That limitation is present in the CBC mode solution presented as well. A random IV will not help you avoid "key rotation" if that's a design requirement. By design, you won't want to rotate the key as the encrypted UUID will likely be stored in external places to refer to the specific user and it cannot change unless you basically persist the encrypted ID somewhere, in which case you might as well have two IDs, one completely random.

The solution is to use hash function. It is fine to cut down hash output so 128-bit from SHA-1 would be fine.

How would you look up the key if it is passed it back to you from another API? It won't be reversible.

If you want to persist two keys, you might as well generate a random second key and persist that. No crypto shenanigans needed.