If its possible please post a pic of your 8600Gt card. Just curious to find the design of the heat sink. If it looks like a normal aluminium block with a fan then cleaning is easy. But if you have the heat sink covered and has small cavities of rectangular blocks on the heat sink, then cleaning is tough.
Recently one of our TE member had the same problem with his XFX 8800GT, inspite of cleaning and reapplying a good thermal paste, the temperature did not come down. The reason, the heat sink has cavities through which the air gets sucked in and let out and the dust get accumulated within the cavities which are hard to clean. I sold one of spare XFX 8800GT heat sink to him and his temperature returned to normal state.
Incase you have a pretty normal aluminium heat sink and if the temperature still remains the same, then reapply thermal paste, if it did not help, then i would suspect the cards electrical components which are about to die.