Yes all old paste has to be removed completely. Arctic also has some liquid for that. http://www.newegg.com/Product/Produc...82E16835100010
Rubbing alcohol or non-oily
fingernail polish remover works too, but not as good.
If you're not using the Intel cooler you don't have to clean it, but if you do, yes clean the thermal pad off first.