Yeah so I was vaguely wondering about some sort of double indirection; the structure keeps track of "this is a pointer I've handed out", those pointers point into that, which then points into the main structure.
I have no idea if this actually a good idea, seems like you get rid of a lot of the cache locality advantages.
This sounds a lot like classic MacOS (pre-Darwin) memory allocation. You were allocated a handle, which you called Lock on to get a real pointer. After accessing the memory, you called Unlock to release it. There was definitely a performance hit for that indirection.
It's the same on classic Windows (pre-Windows 95) memory allocation. GlobalAlloc with GMEM_MOVEABLE or LocalAlloc with LMEM_MOVEABLE returned a handle, which you called GlobalLock or LocalLock on to get a real pointer. After accessing the memory, you called GlobalUnlock or LocalUnlock to release it. Of course, this being Microsoft, you can still call these functions inherited from 16-bit Windows even on today's 64-bit Windows. (See Raymond Chen's "A history of GlobalLock" at https://devblogs.microsoft.com/oldnewthing/20041104-00/?p=37...).
I don't know that the cache locality would be a big issue (your indirection table would be a small-ish array), however you'd eat the cost of doubling the indirections, each pointer access would be two of them.
I have no idea if this actually a good idea, seems like you get rid of a lot of the cache locality advantages.