replacing the the thermal pad does not void your warranty. afterall, the pad is only good for one use, so even if you used the thermal pad the first time you would have to replace it if you ever took the heatsink off. besides, in my experience, all intel (or any other chip manufacturer) cares about is the cpu itself. having you send the heatsink along with a cpu you are rma'ing is just extra hassle for you and the manufacturer (not that they would care anyway, since thermal pads have to be replaced after the first use).
in regards to the thermal pad on heatsinks, the easiest way to get rid of the thermal pad is to soak the thermal material with lighter fluid and then wait a couple minutes. the thermal material should then be easy to scrape off with a credit card (actually, you could probably just wipe it off with a paper towel. lighter fluid does a great job dissolving all kinds of adhesives, including the thermal interface materials). the stock intel P4 heatsinks have a 3 part thermal pad. with these you basically do the same thing. soak the top layer of the pad with lighter fluid. scrape off the thermal material. under that first layer, there is a piece of silvery foil which should peel right off. under that is another layer of thermal material which you just soak in lighter fluid and scrape off. after this, i usually scrub the bottom of the heatsink with dish soap and water to remove any residue (lighter fluid is pretty volatile and evaporates readily, but i'm sure the the stuff you buy in a big can at a grocery store isn't pure, so i think it is a good idea to scrub the heatsink). after you have the pad off, apply your heatsink compound of choice to the processor (and if you are using arctic silver apply some to the contact area on the bottom of the heatsink and then wipe clean with a paper towel) and you are in action.
hope that helps.
--jacob