Is this CPU degradation in my laptop?

Hi I've been having this laptop for 4 years now but I think it has serious CPU problems. It has i7 720qm in it and it has always running hot but nowadays it's completely useless...
Here's what happened:
I bought it in 2010.
In 2011 - idle: 60C, render 95C, games 80-90C.
In 2012 - with cooling pad, idle: 55-65C, render 95C, games 90-95C (!)
In 2013 - stronger cooling pad, idle: 60-65C, render 100C, games 100C (!!!)
1s half of 2014 - HDD corrupted of heat (but I saved it when service couldn't tee-hee)
At this time, I turned on Power Saving and underclocked it to minimum 0.9ghz.
Now ON 0.9ghz it's 72C idle, on stock 1.6ghz it's 82-85C!!! (idle again!)
I thought it's thermal paste problem but I touch the keyboard and it almost melting so hot... and it puts out a lot of heat. Like 2 months ago I wanted to do a memory test (I took out the cooling pad for some reason) and at 40%, it turned off (I think reached tjunction) and the motherboard heat and voltage monitor disappeared. I'm extremely curious now what voltages it's working on but I can't see it .
So I don't know why this is happening, what causes the overheating? I fear that my second HDD will be ruined because some months ago with cooling pad it was on 40C but now it's on 52C!

Have you tried any compressed air to blow out the dust from the laptop?

Dust is the main cause of a computer gradually getting hotter over time.

pbcopter said:

Have you tried any compressed air to blow out the dust from the laptop?

Dust is the main cause of a computer gradually getting hotter over time.

I sent it to the store and they checked the fan and everything was dust-free despite the fact that I didn't take it to clean the fans for years.

badger906 said:

you may have to replace the termal compound on the cpus heat sink. over time it can break down or become less effective, especially if cheap TIM is used, or the processor runs constantly hot.

Yeah maybe I should but how much does it cost if I send it to service to change the TIM? (I tried disassembly but I would just ruin everything so I'd rather send it to someone who knows what's up). And how long does it take for them to reapply the TIM?

linnemeyerhere said:

Depends on the design of the cpu, gpu and there cooler relative to the removable panels. I would hope that a talented tech could do this in under 1 hour and the dab of TIM is minor compared to the labor.

Okay thanks for the answers. I'll send it and see what's happening. I bet they can't keep this CPU under 100C under full load but at least the idle temp should go down to like 40C.