Is your GPU fully seated?, try pulling it and reinstalling it.
Is the GPU cooling fan working?
Is the GPU overclocked?
You may need to thoroughly check out the GPUs heatsink contact, with the GPU itself and the Memory modules.
Also I had something similar situation happen with a 7800GTX, the rear case mounting plate was coming aloose, didn't seem like that would be a problem, but tightening the plates screws solved it.
Just a few suggestions, I know you're frustrated.