One health-care company that I did a project for had a nasty problem with their "provider IDs." These were originally hand-managed and they contained embedded information. A single provider might have more than one ID, and had to know the "right" one to use at each clinic. And, unfortunately, some provider-IDs had been assigned to more than one provider at a time!
To solve the problem and to allow several different systems to communicate with each other unambiguously, I created an internal-only system of surrogate keys: they were simply random strings of letters that were the same length as the old (numeric) provider-ID strings. This was done so that column-sizes and data types didn't have to be changed.
One master system had to take a provider-ID, "figure out who it meant," and return the proper surrogate key, which always corresponded 1:1 to a single person.
Sometimes, that same system had to go the other way ... "which (legacy) provider-ID should we give them when referring to [this_person_surrogate] in [that_system]?"
Each of the downstream systems was now re-coded to use these unambiguous surrogate keys to refer to persons, knowing that every other system would be using only the same surrogate value.
Within each system's database, auto-increment integers were conveniently used as primary and foreign keys, and these keys were of course never shared with any other system. The record for each "person" contained its surrogate.
Any request that one system made to another system always used the surrogate. No system ever knew what any other system's "primary keys" were.
Carrying this concept one step further, surrogate keys were never published externally. The company eventually re-vamped its provider-ID system in an effort to clean up their mess, but when they did so we created a new provider-id "for public consumption," and tied those values to the surrogates just as we had done with the old IDs. Thus, the "purity" of the surrogates was not compromised, and the company didn't have to give its providers "ugly character strings."