As an update: I picked up a bunch of citric acid from a brewing store and set about removing the cats from the car only to discover they'd been completely blown out. Given the car's history I doubt it was some misguided attempt at reducing backpressure, I think they just broke and blew out the tailpipe over the years.
So no amount of cleaning would do them any good, plan B involved installing new catalytic converters.
