"Either we'd add 2 pointer-size fields to PyObject or we would keep a separate hash table (or two) pointing from each object to the info (...)"

The expect a huge impact on the memory footprint. I dislike the idea.

Currently, the smallest Python object is:

>>> sys.getsizeof(object())
16

It's just two pointers. Adding two additional pointers would simply double the size of the object.

"Now the C-API offers a way to switch the allocator, so there's no guarantee
that the right allocator is used in PyMem_Free()."

I would expect that either all interpreters use the same memory allocator, or that each interpreter uses its own allocator. If you use one allocator per interpreter, calling PyMem_Free() from the wrong interpreter would just crash. As you get a crash when you call free() on an object allocated by PyMem_Free(). You can extend PYTHONMALLOC=debug to detect bugs. This builtin debugger is already able to catch misuses of allocators. Adding extra pointers to this debugger is acceptable since it doesn't modify the footprint of the default mode.