Would taking the stock cooler off and putting new layer of thermal paste and new thermal pads help? I'm a bit broke at the mo (actually completely broke..) and am looking for cheapest possible solutions.
I actually just cleaned the card, it was dusty all right. The layer of dust on the fan was really thick. I don't have an air can handy, so I blew into the card using my trusty old lungs. Since I'm a chain smoker, I don't think it helped much.
I cleaned the fan though
Quick update: she's idling at 82C, that dirty bitch.