It seems to be your video system - card and/or drivers then.
If it runs OK in windowed mode then use that, and not full-screen. If you have the CD version, you can set the windowed mode to higher modes than 800 by 600. I use 1280 by 1024 since that is the natural resolution of my flat screen monitor.
The only other thing I can think of is task-tray applications that pop up little displays in the task tray when doing things. Avast anti-virus is an example - I have this, and it pops up a little light bulb now and then, as does mailwasher if it is left to check mail every few minutes. One or both of these, seems to mess with the 256 colour windows pallete if there is a full-screen game going on. Switching them off (after pulling the network cable since if the AV is off, you dont want to be connected to the cable!
) - removes the problem in full-screen.
Cheers
Andy