Try cpu id hw monitor (google it)
I never replace thermal paste unless I remove the heatsink for some reason, which is never. It doesn't go bad, but if you broke the adhesion between the cpu and heatsink by pulling on it or whatever, it's going to need re-doing.