Major overheat at idle for hours! Advice

I bolded my question in case you guys get bored after the first paragraph

I have an Intel Q6600 775 2.4ghz (BO). It idled at 75-80 degrees Celsius for a long time. I did not suspect anything would be wrong with the CPU, because the heatsink was on properly and the provided thermal grease on the bottom of the heatsink was in contact with the CPU. This is also my first time assembling a computer. My FPS with an ATI Radeon 4870 was exceedingly underwhelming (poor to mediocre FPS in just about every 3D game. Some examples include Crysis, TF2, Audiosurf, Warhammer).

While troubleshooting and focusing my attention on the video card, I started monitoring EVERYTHING. Well, I find out that the CPU has been idling at extreme heats (checked BIOS and used SpeedFan). I've been had the computer assembled since Monday and have left the computer on for long periods of time doing installs of two separate Operating Systems (reformatted trying to deduce FPS issue) and downloading already purchased games from Steam, etc. I assume the CPU maintained its temperatures throughout, and I never suspected a thing because everything BUT my FPS in video games was solid

To provide a summary, the stock Intel heatsink and/or thermal paste proved to be massive failures for me. I take personal blame for not monitoring the CPU's temperature earlier, but upon removing the heatsink, I can't see anything wrong with its physical installation and the thermal paste had clearly made sufficient contact with the CPU. I'm going to be placing a Zalman 9700 and using Arctic Silver as recommended. I preface the coming question to be detailed about what the CPU underwent btw : is this particular CPU most likely considerably damaged and worth taking a refund -> restock fee for?

I'm pretty sure I had a thermal shutdown. It shut down during a 3dmark Test during the 2nd CPU Test (this event got me monitoring everything), and, when I rebooted, I was met with a blue screen.

As far as the pins go, the heatsink was very well attached to the board. It didn't budge freely at all and proved almost as difficult to remove as it was to install.