Raptor - the graphics chip isn't replaceable. Sometimes the 7900GTX is, in this case no (at least not as far as I can determine), I already checked.
Replacing the system board is an option, my only reservation is that the board itself might be a bit hard to find and the cost could be pretty prohibitive.
Cleaning out the cooler might help, I agree.
Reinstalling Windows won't though, as the problem occurs in the BIOS too.