Check its consistent with your system settings. Go to display properties - settings, start off at 800x600 and lowest color, then go advance and check on the monitor tab, you are running at the lowest frequency. If this reduces, or clears the problem, keep increasing the settings, till you get a reasonable level. Do you know if you are running at Native Settings to you monitor, most that say they go up to 1600x1200 (or whatever) don't always run well at the maximum level.
What GFX Card do you have, can you get a utility (like ATI utility) that shows the temperatures of your card. It may for example be easier to replace the VGA fan at a cost of $20 / £15.
Note, I have a similar problem that may be completely unrelated to yours, where after one or two reboots the graphics are fine. Not that I know the cause of my problem.