Additional info:
Yes, it's celcius. And yes, everything over 65C can damage your computer
I opened the case, all ventilators were running(LOL I HAVE ONE VENT FOR THE WHOLE CASE AND ONE FOR CPU WTB MORE COOLING). I picked up the vacuum cleaner for the first time of my life and dusted off everything. I'm running the CPU with the case open now and it's sitting at 65C without any heavy load. Still far too high.
Windows PC and 4 years old.
EDIT:
There's enough breathing space in the case, don't feel like checking the paste ATM(need to reserve an afternoon for that).