temperature - Why would my CPU suddenly get much hotter than it used to?

I run an i7-2700K on a DZ68BC, which I've assembled about a year ago. I've used the stock Intel fan without additional thermal compound and it worked flawlessly ever since.

I've had the Intel Desktop Utilities installed ever since I set up the machine. Lately, I've been seeing a lot of these:

I grabbed a can of pressurized air and cleaned out the inside of the case. Didn't do anything in regards to temperature.
So I figured it couldn't hurt to replace the thermal compound between the heat sink and the CPU, so that's what I did. And here's how it looked:

So, I cleaned it all up with alcohol and applied new thermal paste:

So, after this whole ordeal, pretty much nothing has changed:

Before I replaced the thermal compound, I would get temperature reading of >90°C in the BIOS, after replacing it, I got a reading of 78°C.

In the OS, the temperatures are much lower, yet, still concerning. Under moderate load it will jump to the 85-90°C area rather quickly.

Why is the CPU suddenly getting this hot and how should I remedy this situation?

Answer

So, today I've replaced the stock Intel heat sink/fan with an EKL Alpenföhn Himalaya.

Now, shockingly, the temperatures are much lower:

Still a little high though. I no longer get any annoying temperature warnings, so I'm happy for now. After replacing the thermal compound as well as the heat sink and fan, I really don't see what's left to do. Especially given that I didn't see any cause for the sudden increase in heat.