the hotter it gets the faster the fan should spin, at that heat the fan should sound like a harrier jump jet, lol, it should be running at full speed and should only stop when the power does. its either the fan/temp sensor or the fan controller on the motherboard is not working right. I'm leaning towards the fan, can you swap it with another, I realize not everyone has a PC bone yard like I do, a friend/family pc? what we need to do now is replace the cooler or fan or both and verify the problem is not elsewhere, ie motherboard.
Go into the Bios and check/verify the cpu settings are correct, voltage settings, etc. if there is something about the fans see if you can turn the speed to stay at max. if the fan responds and runs at full speed all the time the temps should approach normal. pay attention to the fan after making the changes, is the speed fluctuating or remaining constant? if it is constant the fans sensor may be faulty and in need of replacement