I'm running a 9950 at 3Ghz, sometimes at 3.1 but I get the odd bluey.
I'm using the Ultra 120 Extreme with a 120mm fan on it, the case also has an exhaust 120mm fan at the back and for good measure I've put a 120mm fan intake fan at the front of the case. I'm running in the low 30s at idle, using AS5 tim, the case is a Sonata 3.
My 4870 is kept well cool as well with a HR-03 GT (92mm fan), that thing is mad, low 30s at idle and when I thrash the graphics I am only getting just into the 50s, it's a good setup...
As Gareth has stated look at your case cooling, it sounds like you have checked the CPU out but some AS5 (just enough!) and rub some in/over the heatsink and wipe it off before applying a dot or cross or however you do your tim, it gets into all the little imperfections if you do that, good luck;
hoping that helps,
regards,
J.
Edit. My motherboard is the M3A-32 MVP Deluxe jobbie with WIFI/AP, also the crappy/stupid SB600...