@Clyde I think Linus did a video about it to end the debate once and for all. In the end, it didn't matter because temps were the same.

@retrofreak89 Since you have the paste, I recommend that you try it. Make sure everything is clean, even of finger oil. You can probably find a video online of someone doing this the right way. Use just enough paste for coverage and so it sticks. No more. If you use too much (if you can squeeze it out the sides, it is too much). If too little, you only get coverage in a small area and you are not conducting the heat. Just right is full coverage, no squeeze out (or the squeeze finishes the coverage).

Then, see if the vacuum effect is enough to hold it on and monitor it. You might be just fine. If it starts to slide, well, now you know and you can pull it off, clean it and use a harder thermal CPU compound. Mine has been working and not moving for over a year. Heat, cool and re-heat (power cycles) can make it firmer over time.

@dirthurts Your original post title asks about thermal paste vs. thermal adhesive. To me, these are very similar products--both are thick liquids. The paste typically remains liquid (though very sticky) and the adhesive goes on smooth but later hardens like a glue. Some of the answers above pertain to self-adhesive double-stick pads which is a third method. In another thread we had a mix of anecdotal contributions from folks with different solutions. What I took away from that discussion was:

Double-stick pads (tape?) is hit or miss. A quality product might work fine, but if you don't know what you are getting, you could actually be insulating instead, and that could make your heat problem worse.

CPU thermal compound/paste is probably the best interface between a CPU and sink. (i.e. Arctic Silver 5). Apply to clean parts, and use very sparingly. Friction and suction keep it held in place, but you can still knock or twist it off. It's better if something holds it down (but I have never had a problem with my heatsink on a Pi3 mounted upside-down).

Thermal adhesive may work fine, even if it isn't specifically designed nor documented by the manufacturer for CPUs. It has the advantage of being more secure.

Interface being equal, results vary depending on your heatsink. Most people reported that their Pi2 saw little improvement even with good sink+compound. The Pi3 runs hotter, and I noticed IMMEDIATE and SIGNIFICANT benefit from having a small heatsink attached. Mine was throttling after being on for extended periods, and always whenever I opened a newer game. Adding a small sink with thermal paste has completely eliminated my throttling.

Fans and giant sinks can take the cooling even further. (I use a small sink, and no fan on my Pi3 and I am very pleased).

I would say that for a Pi3, you definitely will benefit from even the smallest of heat sinks if properly attached (I would avoid the self-adhesive gamble).