I can't remember for sure but assume the 8800 uses a heatspreader like other Nvidia gpu's, meaning its quite large, probably close to most cpu's you do, use about the same amount basically. The paste would be fine, but the temps are almost certainly down to dust clogging airflow in the heatsink very badly after all this time. Stock thermal pads/paste are rarely the kind that dries out after a long time like a few thermal pastes can do.
Its very likely the fan/heatsink needing a good squirt with a good airduster. Gpu's seem very very hit and miss in terms of thermal paste and how good the contact is, a decent paste can often drop temps quite a lot. I've actually not removed a full cover type heatsink/block after this kind of length of time, I'm not sure if theres a chance the thermal pads on the memory will be brittle/not sticky after so long and could maybe be a problem when it comes to putting it back together.
First thing to do really is give it a good blast with air duster too see how much dust and how much it drops temps, if its all good and fan can go back to silent/idle speeds, you're set. If not, take it apart, clean it, paste it and whack it back together.