I have been dealing with a P0420 code (Catalyst System Efficiency Below Threshold (Bank 1)) for the past two years, having episodic success with getting it to stay off for a while. Here is the deal... Back in 2007 I got the aging, stock muffler replaced with a cat-back system and a new high-flow cat. Six months or so after this change I got a P0420 light. No driveability issues, just the light. I disconnected/reconnected the battery and put some BG44K in the tank and the light stayed off for ~1000 miles of combined city and highway driving before coming back on. I then replaced the gasket on the rear O2 sensor and tried to clean it. Again, the light stayed off for ~1000 miles. With the light on for the third time, I replaced the rear 02 sensor and again, the light stayed off for ~1000 miles of combined city/highway driving and is now back on for the fourth time.
One other possibility besides the cat: according to the manual (DI-214) for this DTC, the computer compares the waveforms of each of the HEGOs that sit upstream and downstream of the cats. The manual is maddingly ambiguous about what "compare the waveform" means -- I'm sure that the amplitude (voltage) is important, but the silly picture suggests the frequency changes as well (which seems peculiar).
Anyways, the point is that it's not just the downstream O2 sensor that matters. The manual actually says to check HEGO "bank 1 sensor 1" (which I presume is the upstream one) /first/, before looking into the downstream sensor (which you already replaced.)
It may be a little hard to check the upstream HEGO if you lack an oscilloscope or real-time scan tool, of course. You could replace it, or (less good) try swapping the old downstream one in place of the upstream.
-Alex
'97 T100 4x4 5-speed