Yep, the only way to ensure that your identifiers are "permanent" is to choose them such that people have zero reason to change them. They should bear no relationship to any real-world feature that people care about, such as phone numbers, email addresses, national IDs, names, fingerprints, etc.

Random strings fit the bill perfectly. Sequential integers also work fine, except they are easy to guess, so you might need additional security measures.