Before doing anything else, have you reset the BIOS to factory defaults, just in case there's anything in the settings that you have changed that's causing the problem. Don't forget to save or note the settings before you do so.
What other cards are installed in the PC? Have you tried running without all other cards apart from VGA, then adding them back in one-at-a-time until the problem occurs? This is more likely to be a problem where the video card is PCI rather than AGP or PCI-E or PCI-X.
Agreed that a faulty VGA slot is a likely culprit, given that changing cards and re-installing clean OS doesn't clear the problem.
SD