High NO and failing emissions apparently.
Yeah got that after another read through... It was really late...
If your CO and HC are low there is the possibility it is running lean.
There is also the possibility that the EGR is working but needs cleaned (if it hasn't been inspected).
What is the fuel economy like?
Isn't your car is too old for OBDII codes... (again I don't know how extensive OBDI was). So if someone just told you the EGR wasn't throwing codes it's not worth much...
Finally was the car sufficiently warmed up before testing? The cats work best when hot. You say they are new, so they should be working...
1600 ppm NOx seems really high... but then I'm not use to '90s cars...