If you're 'lucky' the CPU could be fine but the motherboard could've suffered "Taiwanese capacitor syndrome," which can cause this sort of subtle and confusing excitement if something goes in the circuitry for the mainboard's voltage regulation. (Anything look subtly bulged or vented?) There's a slim chance this could also have permafried the CPU in the first place, if you want an excuse to lean towards the "test with new mainboard first" methodology.
Another possibility is dust slowly accumulating (or lubricant wearing away) and slowing the CPU fan, while at the same time dulling the effectiveness of the heatsink. If you want to bother caring, you can write down the RPMs you get off the sensor when the thing's new, and watch for signs of degradation... when I noticed my old Mini-Super-Orb (or whatever the beercan-sized dual-fan Thermaltake for Socket A was) had slowed by 1,000 RPM, I knew it was time to ditch the beast and get something more quiet.
Back to the mainboard: If your northbridge requires active cooling (or gets really freakin' hot, even if they didn't slap a fan on it), the same could've happened there, or you could've jammed the fan with a cable and not noticed all this time.
Unless you've got a spare system, or a friend's spare system to try your CPU in, it's probably less work to change the CPU first, and I wouldn't consider the risk of permatoasting the new one very high... on the other hand, since you've got two variables on the mainboard to suspect, it's worth bothering a friend for the $0 test... or finding a hole-in-the-wall shop who'll pop your chip into an open system and let you run a round of memtest for $5 or the purchase of a cable or a stack of blanks. (Hint: The one with cables everywhere, and dirty windows, on the side of town nobody bothers going to; bonus points if they can understand what you want to do on the phone.)
