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

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.

Also, poor performance of UUIDv4 primary keys is most related to how write heavy your table is in the first place, and in particular how insertion heavy it is. In theory your users table shouldn't be very write-heavy, even if it may be insertion-heavy compared to other writes.

Yea, I usually keep a simple incremental ID or whatever is default for internal IDs, and a separate external ID for entities that are presented externally. For security and not unnecessarily leaking info about the number of records, time and rate of record creation etc. UUIDv4 is convenient for uniqueness, but impractical if the ID needs to be conveyed over phone or written down – or used in URLs, so I often use some system for slugs or short codes in addition to the UUID.