High NO is generally due to high combustion temps. It could be caused by things like a lean condition, high engine operating temp, carbon buildup, poor EGR, advanced timing.
It just seems really weird that you would be such a big variation between 15 mph and 25 mph, particularly since you improved on the 15 MPH results and the 25 MPH results got worse. Is there another test facility you can try? Is the tester leaving the car in drive, i.e. is there a chance he is at a higher than normal RPM at 25 MPH by leaving the car in low gear? Is it possible that you have a partial EGR blockage, so that you get just enough at 15 MPH, but when you need more flow at 25 MPH you cannot get enough EGR? Could it be that the car is tested first at 15 MPH, which builds up heat in the motor, so that it fails at 25 MPH?
I would definitely check timing to see if it is advanced, and even if it is on, retard it some to see if it helps. May be try a cooler stat, and let the car sit and cool off before pulling into the lanes. Detonation, even if mild, would raise combustion temps in a hurry. Premium fuel might help if that is the case, so would retarded timing.