Older cards might need the TIM refreshed, too. I just got another HD5870 off the Bay of E. Temps were 92C pretty much instantly, fan at 100%.
Took the heatsink off, and the previous owner had put some sort of cheap silver compound on there, which was really thin and gloopy. It had all squeezed off the GPU core and was puddled inside the shim. Cleaned it up best I could, put a blob of generic grey compound on, reassembled, now getting 69C at 80% fan.
My HD6970 was the same - the factory TIM had all dried up, again dropped 20C and about 30% fan speed just by renewing the TIM.