if you look at the CPU frequency at the high load you can see it's clocked down which is a sign of overheating. it clocks down to prevent overheating because it's unable to get sufficient cooling. you definitely have a cooling issue of some sort. it will only get slower and hotter until something breaks or it goes into thermal protection mode and shuts it self off.
Thanks! Of course, the computer is of adequate retirement age (it's going to turn 15 in August) or to be relegated to server duty, but it won't hurt to make sure the thermals are all good.
Addendum, that 'similar temperatue on high load' is because it's thermal throttled at that point. See that it went from 2.9GHz to 1.6GHz. It won't ever reach 100 degrees or close to that because of this safety feature.
if it blows hot air, that means it successfully transfers heat off the cpu, so the blame is not entirely on the thermal paste (you should probably still change it though). clean the sink and the air intakes, laptops insides easily get tightly packed with dust.