Thanks for the response guys.
Yes sorry euan is my colleague so this is the same problem. We can consolidate his question here. Sorry about the duplication.

Which version of Java6 are we talking about?
They will be using Java 6 consumer JREs. Any of 6u2, 6u3, and maybe some on 6u4.
One guess is that Java 6 uses the (old version of) Direct3D pipeline when
in full-screen mode. That may have backfired somehow on Intel or SiS chips
(providing that the d3d pipeline was indeed enabled on those boards)
since they really do suck in d3d.
I've done a bit of research. If my understanding is correct, Java 6 introduced the Direct3D pipeline and made it default for Fullscreen mode even though the old DirectDraw/GDI one was still default in windowed/desktop mode. Is that correct? So to go back to the Java 5 behaviour we explicitly disable the Direct3D pipeline.
Could you ask your users to set J2D_TRACE_LEVEL=4 env. variable
prior to starting your application if possible and collect the output
in the console (providing they start it from the console)?
A workaround would be to set -Dsun.java2d.d3d=false and see if it helps.
Our app starts using Launch4j/javaw on Windows so I think I'll try disabling the D3D pipeline first and see if that helps. But I will endeavor to get some trace logs to see if the real problem can be diagnosed. I have the usual problem - all folks affected by this are remote

.
Thanks for the suggestions. I'll come back when I know more.