DB lookups + extra index are way more expensive then hardware assisted decoding.

If your UUIDv4 is cached, your still suffering from extra storage and index. Not a issue on a million row system but imagine a billion, 10 billion.

And what if its not cached. Great, now your hitting the disk.

Computers do not suffering from lacking CPU performance, especially when you can deploy CPU instruction sets. Hell, you do not even need encryption. How about making a simple bit shift where you include a simple lookup identifier. Black box sure, and not great if leaked but you have other things to worry about if your actual shift pattern is leaked. Use extra byte or two for iding the pattern.

Obfuscating your IDs is easy. No need for full encryption.

Hardware assisted is a red herring here. As you noted the real problem is that random reads have poor data locality, which degrades your database performance in a way that is expensive to resolve.

Why would it be computationally complex? The encryption is implemented in the silicon, it is close to free for all practical purposes. The lookup table would be wildly more expensive in almost all cases due to comparatively poor memory locality.