5870 Astronomical temperatures. Need help asap

Hello. I own a non-refference sapphire 5870 (http://www.newegg.com/Product/Product.aspx?Item=N82E16814102883) that is 2 years and a half old and I have quite a problem with it. Around a year ago, a friend of mine purcheased some artic silver 5 and asked me if I would want a round for my cpu and gpu. I proceeded to install the paste, ran a furmark and was happy with the new temps which were like 5*C lower at full load. Since then I started to experience artefacts with overclock, even though the temps were fine... I said k... no more ok on this gpu ever. A month ago, far cry 3 was released and i could'nt wait to try it out and see how it performs so I fired msi afterburner up for the OSD of temps and fps and after not even 5 minutes of gameplay (more like intro) the card reached 77*C and it started having artefacts. It seemed very strange that it did that at a relatively low temperature so I manually set the fan to go 100% at 75*C. 2-3 days ago I played for the first time Trine 2 with afterburner runing in background and at 72*c it went off artefacting again. I searched google for a solution and found somebody with the exact same problem as me and only 1 reply :"Check the sensors in gpu-z". So I fired up furmark along with gpu-z and msi afterburner to take a look at what was wrong. This came up : 

Take a look at Gpu Temp #3... And that is not the highest it ever went. I am amazed that the card even works anymore after so many hours playing games at temps much higher than this. After finding out this, I began to search google for a clue to what hight help, but could'nt find a precise answer. Some suggested it was a specific cip, but when I touched it, it was cool... others that is a part of the die, but if the normal temperature goes up or down 20*C, the temp #3 stays still and doesn't react. Any help or suggestion is of tremendous help to me.

Additional info: The artefacts consist of formations made out of 6X6 pixels (around 30-40 total) scattered all over the screen that change colour every new time they appear based on the scene on the screen. If I spam alt+tab and alt+ctrl+del I got to the task manager and eventually desktop after 20-30 sec and can go back to continue the game like nothing happened.

When I installed the thermal paste, I cleaned the die and heatsink with medical alcohol (which is the best thing I can get for under 20$ in my country) and cotton. Any suggestions to what would be a good alternative ? The CPU still does great under prime 95 and was treated exactley like the gpu.

Also, many sugested checking the spreadsheets but I can't seem to find any.

Thank you a lot for reading.

that thermal paste is conductive so when it heats up it speards out and it could be shorting somthing just a thought.

Thanks for the advice, will check if it leaked out or anything and be more carefull when replacing it. Any suggestions on what might be a good alternative from your experience ?