Hi everyone! Posting this from the media center :-). With the termal paste (and no fan) and undervolted to 1.25V, the system idles at 35° and stays at 43° after a few minutes of stress with 4 threads, being more or less inaudible. So all is working as I wanted. I would like to thank everyone for the great advice.
Never use no paste. It is important to get really good contact.
What kind did you use now? There are silicon based and silver ones, silver is a far better heat conductor. (But you have to be carful since it is also one of the best electric conductors.) Normally I use some of the fine milled silver grease. Boxed coolers often come with some silicone based attached which is also ok if you just want to set it up quickly. And it is less liquid (more like chewing gum) and it should not have much electric conductivity if you spill some of it.
It was the OEM paste supplied with a Cooler Master V8 I bought for my Phenom II X4 940 BE (for which I used another one). It seems quite "solid" and has a dark colour.