Saltwater, astounding pressure and marine organisms make for a far harsher environment than the vacuum of space, or even a botched re-entry.

That said the argument I heard was that by the time they fall apart, the Pu has all but decayed.

The argument you heard is correct. The casings are likely made of something that is completely unaffected by saltwater, the pressures involved are neither astounding nor even interesting in this context, and... marine organisms? Which ones? Harsher than a botched re-entry?

The casings are steel, the rtg is in a ceramic capsule. You'd be amazed at what barnacles and such can pry wide open given time.