Just an update on this. They finally delivered the new cooler yesterday and me and my friend installed it (with some difficulty). Took us about 3 hours, but we got it done and the system is fixed now.
My temperatures are around 25 to 30 degrees when idle and I couldn't get it to go above 55 or 60 even when running stress tests and games. So it works. It's also much quieter than the old model, which is great.
The cooler came with it's own thermal paste already applied (we carefully removed the old stuff), so I hope that's ok to use.