Otherwise, if things only sometimes fail, it results often from incorrect threading.
Yeah, maybe I should put the game in a state where nothing is updated or drawn until the change has been achieved. It's just that this is all called from one controller-class, so it should never trip over itself. The changes should be executed completely linearly.
It could be because you keep dumping the frame everytime you switch modes. Try using a single JFrame for the entire lifecycle of the game whether you are in fullscreen or windowed mode.
Hmm, yeah I'd like to do that, but there are some reference-problems associated with that.
Can't assume such things unfortunately

never hurts to print or dump the error into a file for exceptions such as those.
I'll definitely do that, and see if it ever fails.
In conclusion, it could well be all these three rather simple things. Thank you very much for your inputs. I guess I have an evening of destroying my graphics adapter in front of me XD
I'll post back if I find a solution that keeps the weirdness away.