This!
I recently worked on a system that was having issues. Yes, the fan was running on high and no the cooling fins weren't clogged. BUT! It turns out the heat sink had poor thermal contact with the CPU. The heat sink base was slightly warped. replacing it with a good aftermarket heat sink took running temps from 80C+ at idle to 43-45C under full load. Miraculously all the problems went away, as if by magic. The client had been told by two other techs to trash it.