DeepTechScuba once bubbled...
Dr Saturation, I would not automatically rule out contamination. It certainly is a possibility. Trying nitrox from another vendor might help answer that particular possibility.
It is also possible that the tank has been contaminated, and upon filling, this is causing the contamination. Inspecting and cleaning the tank might be needed.
I am surprised that you jumped to the conclusion that "its unlikely to be contamination." That would be the first thing I would wonder about.
Headaches are normally associated with CO2 retention. Even though this is nitrox, proper breathing might be the cause. Is the diver skip breathing? Is the diver not breathing regularly or deeply enough? Shallow breathing could be the cause. That would be the second thing I would wonder about.
I also agree with you, that this person may be predisposed to OxTox and therefore a leaner nitrox mix and diving shallower might be warranted.
MikeF mentioned ear clearing. That is certainly possible as well. This is what I call "thinking outside the box." Bravo.
You're concerns are all possible DeepTechScuba.
I considered these too, but my reasoning is as follows:
Its not likely to skip breathe with nitrox alone, said diver would do it on air too;
Ear clearing issues, could be too, but why only on nitrox? Equalization are more related to compressed gas, not specifically 02 content;
Contamination is possible, but nitrox costs more to setup than air, and the risk for fire and explosions, depending on how the nitrox is mixed, are greater if the gas and gear are not cleaned to 02 standards; hydrocarbon contaminants are less likely because nitrox air has to be cleaner from the get-go;
Contamination with air fills is more common because all that's needed is a particulate filter and an uncontaminated air intake line;
Tanks can be contaminated, but usually the contents do not cause headaches;
Again, you are right, there are lots of other possibilities.
I'd be very interested in what IzzyTahil does to correct the issue. Please keep us posted!