I think you are misreading the emissions numbers. nj300se's engine is actually running lean. Although it is true that he failedfor slightly higher HC, that in and of itself is not a sign of running rich. A prime example of this is what is known to emissions people as a lean misfire. A lean misfire will produce huge amounts of HC emissions, but the reason is that the engine running too lean for the fuel to ignite, and the raw mixture gets dumped out the exhaust.
A lean misfire is an extreme example, but anything that can keep fuel from burning will raise HC. Carbon deposits soak up gas during intake stroke and release it during exhaust stroke. This gas isn't vaporized so it doesn't burn and comes down the pipe raw. Cool combustion chambers can keep gas from vaporizing, but we know this can't be the case
because in nj300se's engine because the NOX is so high. NOX formation requires very hot combustion chambers, on the order of 2500° F. Rich engines run cool. Lean engines run hot, and produce more NOX.
For diagnosing the cause, the most important gases to look at are CO, O2, and CO2. CO is a very good indicator of richness. CO will start to climb rapidly even before excess HC shows up noticeably in the exhaust. However, CO is not a good indicator of how lean an engine is running. Once an engine goes leaner that stoichiometric, CO flattens out and doesn't tell us much.
O2 on the other hand is a not a good indicator of richness, but it will tell us how lean an engine is running. O2 starts to climb on the lean side of stoichiometric. This is because with lean conditions there are fewer HC molecules to unite with the O2 molecules. The leaner you go, the more O2 there is. With a lean misfire O2 will skyrocket.
Finally, CO2 is a good indicator of combustion efficiency. CO2 should be above 14% at the minimum. Higher is better.Low CO2 tells us that for what ever reasons, combustion is not efficient and the HC and O2 molecules are not uniting as they should.
In the case of nj300se's engine, we have over three times the percentage of O2 as CO. This indicates an engine running a bit on the lean side. A vacuum leak could cause this. Old leaky injectors which dribble instead of spray can cause this. Dirty carbonized combustion chambers can cause this.
To reduce NOX you want the combustion chambers to run cooler. Good flow in the cooling system through the heads will reduce NOX. An out of spec coolant temperature sensor can cause an engine to run hotter; make sure the ECT is in spec. Worn impeller blades on the water pump can make the heads run too hot. Running richer cause cooler combustion and will reduce NOX. Clean combustion chambers and lower compression will lower NOX. Avoiding detonation will prevent NOX. Always run high octane gas when you want help passing a NOX emissions tests. De-carbonize the cylinder head, which lowers compression, allows for better heat transfer, and more efficient combustion. De-carbonized heads will produce less NOX and less HC.
EGR reduces NOX by reducing the oxygen content of the mixture. This serves to effectively enriches the mixture as itforces the ratio of HC to O2 higher. It also causes the combustion to occur slower and cooler because there is less
oxygen to fan the flame. This also prevents detonation and knock. Unfortunately, many EGR valves are replaced without
cleaning the EGR passages in the manifold. Often the EGR valve itself is good and the passages are choked with carbon blocking EGR flow. Always check the passages before replacing an EGR valve.
I think a good emissions tech could get nj300se's car through emissions without a new cat. But finding a good emissions tech can be a problem. Japanese cars rely heavily on the catalytic converter for NOX reduction. My advice for nj300se would be to take care of all the small things which can be done, and then replace the catalytic converter with a new OEM unit.