The smudges or staining on the heat spreader have nothing to do with a change in temp.
Any of the top 25 TIMs produces the same temp within 2C. CPU temp is affected by ambient room temp also. You only need a very thin film of TIM. More TIM is NOT better as it's only intended to fill imperfections in the surfaces of the heat spreader and heatsink base.
Building a reliable PC involves more than just assembling the parts. You need to be able to configure all of the BIOS settings appropriately. This can be quite involved and frustrating as it can require a lot of trial and error with stress testing. It is however often the only means to get a 100% reliable PC.