I am in pretty much the same boat with a '99 Cali. 4Runner and I did the A/F sensor at 90k--I'm at 110k now. I get a P0420 every few months (I keep a log). Last one was in June. My sensor voltage profiles do look normal (I have an OBDII linkup to my laptop that lets me see.) This has been going on for 2 1/2 years and I passed emissions about nine months ago. In NJ they just pull codes anyway. I believe the trigger algorithm for the P0420 is oversensitive or perhaps can just be triggered by some unusual driving profile. Anyway, my suggestion is reset and see what happens before you shell out $1800 bucks for cats. I would rather reset and ignore 3 or 4 times per year, especially when I can see the performance is actually there.