CPU Overheats After Thermal Grease Application

Heatsink or fans. Either is more likely than the thermal paste being the problem.

And the heatsink, fan, and everything else was decently cleaned when?

And I find something funky with your idle temps. Most air-conditioned rooms, are around 72°F or 22°C and with it being impossible on an air or liquid cooled pc to be below ambient temps, most pc's at idle run in the 30-40°C range. So for you to be concerned about the pc now running 8-18°C (46-64°F) would mean the area around the pc would be close to 0°C or 32°F for that to happen.

Oh, and a heatsink is nothing more than a machined chunk of metal. They don't die or break without some user intervention. If it's clean, the fault lies with the fan in some manner, either not spinning according to settings (worn bearings) or the settings in bios/software are not right for the fan/temps reached.

The 4300 has a TDP of 95w, so thermal shutdowns can occur at anything close to that. But there is one thing to remember, software as far as temps goes, is all relative. Nothing is perfect. Hwmonitor and core temp, while widely accepted as good reliable software are still subject to things like user error (running both at the same time) and Hardware limitations. Different boards from different manufacturers, from different series to different chipset set will all report differently, the software looks for 1 sensor at 1 point and on 1 board that sensor is part of the package, on another board it could be part of the Northbridge, and since Intel has on-die Northbridge functions, that can play hell with temp readings.
Does your cpu idle at 8-18°C? No way, not unless you live in Siberia and it's winter time and the pc is by an open window. Even a good liquid cooler at max fan speeds (h100i for instance) will only be able to cool a cpu to within 3-6°C above ambient temp, so if your pc area is 22°C (72°F) you are at best looking at 25-28°C (77-82°F) and a stock cooler or something even better like a hyper212 EVO will be higher than that.

As far as fan speeds go, you'll have 2 clues. Pop the side on your pc, and look/listen to the cpu fan at idle. Now play your game or stress test, and watch/listen to the fan as the temps start to rise. Unless you are that unfortunate to have a set single speed fan, even a basic stock fan should speed up with the duty cycle set in bios, until it reaches max speed at 70% duty cycle, or roughly 70% of the temp the cpu is rated to handle. If it doesn't spin up, you'll need to check bios settings and make sure the fan details are set for 'performance' not 'silent' and barring that make manual adjustments to lower the max duty cycle, which will raise the speed of the fan at a lower temp set point.

Considering how far off idle temps are reported by both hwmonitor and core temp, you sound like you have either faulty temp sensors, or one of those boards that just doesn't play well with those software. Try real temp, speccy, hwinfo, as alternatives, one should read more normal temps hopefully.

Bad fan. Figures. The speed sensor was fried, so was not running at correct speed for temp, and was reporting wrong speed as well, further screwing things up. Glad the new fan fixed the issues