Yep, lose the pad, but don't scrape it. That could scratch up the bottom of the heatsink. Rather, use something like GooGone to get the bulk of it off, then follow that with isopropyl alcohol to get all the residue off. That will leve you a nice, clean, uncontaminated surface.
Then use Arctic Silver if you can, but even standard white goo is better than the pad.