Overheating CPU, advice required

Intel i5-2500K
Gigabyte Z68A-D3H-B3
Radeon 7950, not that it should matter

I've been noticing spikes in my CPU usage, I downloaded process explorer and tried to get to the bottom of which process was causing this.

Now I have a feeling that the CPU is overheating which is causing the high CPU usage.

This is when the system has nothing ruing but Chrome (Not overclocking by the way), when the PC boots its around 35°C, ruing a game makes it reach 80°-90°.

I run the Intel diagnosis tool and it failed after some time when it reached the max temperature, so I cleaned out my fans and reapplied thermal paste, this time it reached a bit farther in the test but still failed.

1. Could this be because the cpu itself is faulty somehow?
2. I'm using a simple fan, like this one http://thumbs.ebaystatic.com/images/g/RvYAAOSwirZTxVOD/s-l225.jpg, I'd still think it shouldn't be reaching high temperatures, right?
3. Should I buy a stronger heat sink / fan or is there some way to test the CPU to know more?

Any advice would be helpful, and I can provide any more details upon request.