I had the same problem and i solved that changing the original cooler for a Corsair model.
Pay attention about your chassis air flow.
Thanks for sharing! I'm sure I could buy a fancy cooler and have the temperatures lower, but it should just work out of the box. I'm looking to find the root of the problem. My airflow is great though, so that cannot be the issue.
I did observe something odd when I removed the cmos battery and replaced it, then rebooted.
On the XTU stress test, the frequency quickly changed and the voltage changed to perform it.
However, when I tried to run a game, the frequency and the voltage refused to change, so my game was slow until I manually changed the frequency.
With OC Genie on, the frequency doesn't change from whatever I manually set it to be. With OC Genie off, the frequency can't get high enough to do any real processing.
I'll have it taken to a shop soon to check everything and diagnose the core issue.