I don't have any thermal paste... But what is your opinion on the temp before i got the CM cooler? It went up till shut down. Maybe the cpu has some fault?
Your cpu was extremely hot at 110C. But, I'm not sure which 5000+ you have. There were several with that designation. Athlon x2, Athlon 64 X2, Black Edition... and several variations on those. Either way, 72C is around the max temp for most of those, I believe. It may be a voltage regulator over-volting the processor, or the processor itself causing the high temp... if the cooler is installed properly.