To be thorough try with a different PSU as you mention. You can also remove additional components for troubleshooting failure to POST.
If things continue to fail. I'm more inclined to say BIOS issue or component failure on the board if testing with another PSU doesn't resolve.
Thermal paste doesn't remain tacky and pliable its entire life. In fact, it will eventually become dry and crumbly. However, it is still able to perform its job by providing a conductive interface between the top of the CPU and heatsink.
Its effectiveness is diminished if removed or disturbed, but otherwise it will work for many, many years. Let us know what you find

Good luck!