And continue this concept downward. Except when it's inside your org, you're the registrar of your namespace's sub-OIDs, and so on. And there's precisely no reason not to have hierarchical sequential ids for everything. You need to generate ids on 100 servers? Good, give each server a namespace. You need to do that in a 100 processes on each server? Good, give a sub-namespace to those too.
And the best of all is that the above-organization OID part of the tree is ONLY needed if you show these ids outside your organization. Otherwise you can use the internal private part of the identifiers.
So what am I missing here? Maybe they need to be hard to guess, so add a random key part to them (distinct from the generated sequence part) as a "password". Done.