I had this issue with a brand new 8800gt. If you are pretty sure it isn't related to heating damage, here are some things you can try:

- Install different drivers
- New power supply (Not enough amps on the 12v rail can do some strange things)

Installing a different set of drivers is what solved it for me. The newest nvidia drivers didn't solve it. I ended up installing the drivers that came with the card. Hopefully I'll be able to up to the latest drivers in the future.

Best of luck