Why do you think this isn’t reorg safe?
The format of locations is block_height/TX_index/output_index.
So if you experience a reorg back to block_height H you simply delete all locations which’s block_height > H from the expired UTXO set, and you add all locations which were spent in blocks that were reorged out.
However, I like your idea that you can replace expired UTXOs with, e.g., a 20-byte hash. That simplifies the scheme significantly, makes it cheaper to spend expired UTXOs, and still prunes about 75% of all spam.
Edit: Oh, now I see your point. There could be a UTXO which expired on the previous fork, but was spent on the reorging fork shortly before it expired. Then you would have already deleted it from your utxo set and can’t simply restore it to verify that valid block.
However, you can restore that deleted UTXO from its ‘location’ as long as you still have the block at block_height, in which that UTXO was created. And if you don’t have that block you can request it from your peers.