Consistent Problems with thermals

My friend, currently running an AMD A10-5800k with a stock cooler, is having issues with his computer shutting down during gaming. We fixed this problem in the past with cleaning the CPU/fan and replacing the thermal compound. It has been fine up until this point (around 6-8 months) and the issue is back. He has had this computer since we built it in early August of 2013. I think it is very strange that we would need to do this so frequently with his computer. While I have had my computer around 5 months longer and I have not needed to change the thermal compound at all. 

have you tried a 24 hour prime 95  run? Make sure you record logs and temps and see if it is the CPU

Also coolermaster makes a good heatsink for like 30$ 

What is the thermal compound you are using?

Is your motherboard set set up stock and are you over clocking it?

The thermal compound is cheap. We needed it soon so we bought it from a local computer shop for around $7, I can't remember the exact name off the top of my head. And we are not overclocking anything in his PC.

Should I do the prime 95 run before I put new thermal paste on?