1. You mentioned hesitation and the higher readings happening then: Is it possible fuel flow interruption? Maybe put a gauge on the fuel rail and watch for pressure fluctuations?
2. So, your O2 sensors are indicating a "lean burn" condition. Lean burn produces NOx due to higher combustion temperatures (and is the whole reason for the EGR system).
Try this for grins. Go one heat range colder on your plugs. And then if that doesn't work, go to a lower temp thermostat. All of this is to lower engine temp in order to help lower combustion temperatures to reduce NOx. This is only for the test though, as I would go back to regular plugs if the cooler plugs "fixed" the NOx.
Another option is to use water injection to lower combustion temperatures, but with the standard plugs.
If it were me, I'd try the water injection first.
https://www.roadandtrack.com/new-cars/c ... orsepower/
https://www.motortrend.com/how-to/impp- ... injection/
And you don't have to buy an expensive kit either. You can make your own with a washer bottle, a small pump, and a spray nozzle. People have been doing this since the 1960's due to higher compression and poor gas quality. Since you are just trying to pass the test, it doesn't need to be active after the test either. You could use your existing windshield washer bottle, and just get an auxiliary pump for short term use.
Oh, and as a last thought, if they still have your old cats, have them install them after the new CA cats to maybe help with the clean-up.