I've never had any issues with AS5. The Zalman CNPS9500 cooler on my old amd x2 broke after 5-6 years (the fan dismounted off of the motor) and the temperatures weren't even ridiculous with the cooler running passively with the 5-6 year old AS5 paste. I'm running mx4 now, but only because I wanted to try something different.
I've never used the stock intel cooler, but it definitely sounds like you're having a seating issue. When I installed an AIO watercooler on my video card I first tried to use a ziptie mount and couldn't get good enough pressure to keep the gpu optimally cool. Now with a bracket giving me better seating pressure the gpu runs another 10+ degrees cooler.
edit: My bad didnt see this was solved, glad to see you figured it out and it was a seating issue.
On a sidenote... the cooler master 212 I have on my second system does a great job at cooling the 6 core processor underneath.