Windows desktop 'flickers through' in full screen mode

When I launch my game in full screen mode (it changes to 800 x 600 - my Win XP
Desktop is normally at 1600 x 1200), sometimes bits of my Windows desktop
flicker ‘through’ the game - i.e. you can see bits of the windows desktop - the
start button and taskbar usually.

It flickers for a bit then usually goes away (maybe after 10 seconds or so), but
looks bad.

I see this on several test machines. I’m using SDL, software mode.

Any thoughts?