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.
Stop TCPA, stupid software patents and corrupt politicians!