They are created consecutively, not randomly, per salesforce instance (e.g. na3 will have its own pool of numbers). Within a single org, the ID values will never be duplicated, and even all throughout production, no Id will ever appear twice (because each ID also includes a "pod Id" to identify the origin of an Id). Cloning an org (e.g. a Sandbox) will result in identical Id values in both orgs, but that's the only time a single ID will be used more than once.
Salesforce does not currently recycle its Id values, so no org in production will ever have the same record Id for two different records, even if records are deleted and created later. Salesforce is currently using only a few percent of the available Id values, so they wouldn't need to worry about expanding or recycling ID values any time this century.
Note that your example ID values are incorrect; the last three characters are derived from the first 15 characters. See What are Salesforce ID's composed of? for more information on the internal structure of Id values.