I like the petname approach that GNS[0] takes - there are stable identifiers (they're public keys) but users are meant to refer to identifiers using local names (or names that their contacts have set).
Generally, using cryptography or associated cryptographic functions is the way to go when trying to make robust systems. Joe Armstrong has a great talk where he outlines how to create a content addressable store for storing and working with knowledge/data. He suggests using SHA256 content hashing because giving items of data unique names is a hard problem so we might as well name pieces of data by their content hashes and then have a human readable pointer.
[0] https://tools.ietf.org/id/draft-schanzen-gns-01.html