Not a retroactive solution but for the future, it seems like an obvious solution is serial number tracking.

Make it illegal to purchase or sell a catalytic converter (or really anything of sufficient value) without a legible serial number, and maintain a database of serial numbers along with associations to a VIN. If VIN X has been totaled or the owner of VIN X decides to sell his old cat, it is legal to remap Catalytic Converter 1234 to VIN Y.

Additionally, if, during state inspections, VIN Y is found to have catalytic converter 5678 which was not originally associated with VIN Y, figure out what car it came from and what the status of that vehicle is, and what shop the vehicle owner acquired the cat from.

I guess this is more "paperwork" but since 100% of it can be digital, so what? This kind of tracking is already done with firearms in the US.