If it were me, I would get a way to look at the actual live values of the fuel trims, O2 sensor readings, MAF reading. You can for sure diagnose if it is an air leak with a scan tool which lets you see all of these things, live, preferably on a chart. I am sure you know this, but the PCM looks at the MAF and then sets a preprogrammed amount of fuel by adjusting the injector pulse width. It then looks at the O2 sensor before the cats and it adds or subtracts from the programmed pulse width by adjusting the fuel trim. When the fuel trim gets about 25% away from the preprogramed value, you get the lean or rich codes. What you should see is your fuel trims maxed out and the PCM will not adjust more than so high to compensate. So you could have a dirty MAF, I am assuming you checked/cleaned it and you can verify it is working (again I think you would benefit from a scan tool that can see everything live). If you have an air leak, your fuel trims will be the greatest at idle and will go down as you go up in rpms. You can spray the combustible of your choice around your potential leak points and you can see the fuel trim cut back if you have a leak. To me, it sounds like fuel delivery or a bad MAF. As you go up in rpms, with an air leak, the fuel trims should go down when compared to idle.
I use FORSCAN and you can see live graphs of your fuel trim, O2 sensors, MAF flow, rpms, load, etc. I would start with something you can see what your PCM is seeing to help with troubleshooting.
If you are thinking it is plugged catalytic converters, you should be able to diagnose this with a vacuum gauge.