I always take the feet off along with anything else that's on the bottom if it can be done without leaving a mess. From my experience, the Velcro patches adhere better to bare metal. When applied to a rubber bottom (or foam like on EBS pedals) the seal never lasts and the pedal inevitably comes loose and bangs around in the case. Ex: BBE Sonic Stomp or Opto Stomp pedals have a large, unevenly surfaced rubber pad that covers most of the bottom in lieu of individual feet. You can peel this whole thing off with little to no residue if you go slowly. EBS pedals however, I don't even try to remove anymore. That foam is attached with industrial strength glue and removing it is a hideous experience. No amount of goo-gone will get it all off. With EBS I use the double-backing methods mentioned earlier in this thread. But if I can get a completely even, empty surface free of feet, rubber pads and/or foam backing that's my preference and I almost never have pedals come loose.