ALWAYS use Dual Lock.
If you have trouble getting a pedal off, well, that's the whole point isn't it? It should be difficult. But, use a flat-head screwdriver, or some similar instrument of destruction to lift the pedal off. Once one edge has lifted a tiny bit the pedal will come off easily.
Dual Lock lasts almost forever, a lot longer than Velcro, and it doesn't collect hair, grass, whatever is drifting around, nor does it tamp down. And it almost never leaves a gooey mess stuck to the rails or pedal.