I doubt the thermal paste can change the temps by ~15°C, but might look into it. Does the paste lose it's features over time? I used the paste provided with the cooler this time, but before that it was arctic silver. Didn't really change the temps.

Wrote to AMD to see if they will be willing to do anything, if not, then I guess I will be looking around for a different CPU. My budget is as low as it gets atm, I'm usually aiming for best bang for the buck though.