I don't understand why you need to maintain two separate keys: instead of generating a random key, why not just encrypt the auto-increment key using a secret key? This is the approach used by e.g. cloud providers that use auto-increment keys internally but don't want them to be guessable.
I think the biggest problem with this approach is it effectively pins you to a encryption key and algorithm (unless you embed some information in the key that lets you version the key, gotta think of that upfront).
Imagine, for example, that you picked DES and "kangaroo" as the secret several years back. You are now pinned to an algorithm and key with known security problems and a weak key.
Especially since you can try the encryption algorithm.
Create 1000 users very quickly in a row and you now have 1000 samples of enc(i) all the way up to enc(i+1000) that can help you break the algorithm.
Not saying it will be easy but it surely lowers the guarantees given by the encryption. Someone better at crypto can probably quantify this risk better than me.
Sure, that works too. The upside of just storing a random string is you don't ever need to deal with secret management, key rotation, ciphers getting broken, etc — the random string truly has nothing to do with the real underlying ID, so there's just less work involved in hiding it. The downside is some extra bytes and index space.
