> the deep-frozen objects also reference the small ints directly, as well as the singleton for b"".
> Is this even safe across Py_Finalize()/Py_Initialize()? If not, we'll need to roll that back as well.

The small ints and the empty bytes object each have "immortal" refcounts too (999999999, just like you did in deepfreeze).  So they would cause a similar behavior to what Victor reported.  Otherwise I wouldn't expect any problems across Py_Finalize()/Py_Initialize().