I'm having this same issue I had the code ran the first time and it came up with a p420 or something. The shop immediately said you need a new catalytic converter. I went to another shop thinking the first one was trying to pull a fast one. Without even looking at the car they also said a new catalytic converter. Discouraged I went home to start saving money. The lights then turned off automatically a month later and I passed my emissions and inspection and had no check engine etc lights for over 6 months after without doing any repairs to it. Now it's back. Ugh! I'm questioning my local shops as I feel they couldn't see past the dollar signs floating in front of their eyes but I'm at a loss as to what to do/check. The car drives just fine, but the traction off will be a problem when the winter snows start. So really hoping to figure this out. I am not mechanically inclined but if I could tell a shop what to replace they perhaps won't put blinders on.
http://www.toyota-4runner.org/4th-gen-t4rs/132953-toolbox-how-use.html#post1272379
It's a bit dated and I need to update information in that thread one of these days, but it gives a rough explanation on what's going on with the P0420 and why most shops default to "you need a catalytic converter."
In my experience with Toyota, it's a fairly accurate assumption/result when you get a P0420 and/or P0430 that it's the catalytic converter. The Oxygen Sensors can sometimes be the culprit, but that's not as common these days on OBDII vehicles as it was in the older days.
Realistically from your description it sounds like you have a catalytic converter that is "borderline" which means that when it "passes" the on-board test it does so by a small margin (which is why it failed before and then went good for a while and failed again). There is the slim possibility that it could be an oxygen sensor, but that's more of a "we can try it if you want since it's cheaper than new catalytic converters, but there's no guarantee it will fix it."
Realistically there's very little testing methods you can do to check the actual function of the catalytic converter as everything is inferred from what the ECM determines based on the Oxygen Sensors. But the sensors have a very narrow operating range so if they were bad or borderline other DTCs typically pop up in conjunction or instead of a P0420/P0430 (Oxygen Sensor too lean/voltage issues/out of range/ect.) Additionally it also comes down to "do you want to pay more than an hour of diagnosis?" IF I had a 5-channel gas analyzer, heavy duty digital oscilloscope, 4-wheel dyno, access to the factory information on all the sensor data (not always in the FSM), and about 4~8hrs to test every single component at a level most shops would never think of doing I could tell you with 100% certainty if the Catalytic Converter was the only possible failure point. BUT you as a customer aren't gonna foot the bill for all that extra equipment (because equipment like that doesn't come cheap or gets used often so investment vs. return is very poor) and the 4~8hrs of diagnosis. Most customers are trained to think that everything can be fixed in an hour and when it can't it's the company/technician's fault, but sometimes diagnosing something takes more than the flat "1hr diagnostic fee."
Plus most of the information we get from the vehicle means nothing to the customer, I could have reams of data, FSM troubleshooting charts, personal notes, ect. and a customer still wouldn't believe me when I tell them the repair is gonna be $2000 because for some reason people (most who weren't even alive then) still expect repairs and parts to cost like they did in the 1940's. But if they get an oil change done and they lose .5mpg afterwards on their next fill-up I broke the car on purpose. It's a lose lose industry for everyone these days.
Post Note-
Not trying to sound like I am blaming you or you guys in general. Rather trying to show what it's like from my experience as a technician.
