Gee, I just used the self-adhesive strips that came with the gaiters and the pieces are still attached two years and many miles later. I use Montrail Hardrocks and they have a smooth spot on the heel just under the logo to which the velcro sticks just fine. If you have mesh or something porous on the heel then do what Lori suggests; put a spot of epoxy on first.
This is what I ended up doing. It's held up so far! The heels are kinda squishy on my shoes so it flexes a lot. and eventually they start to peel off at the bottom. Thanks!
Barge's cement and Duco Home contact adhesive both work pretty well. The trick is 1) clean surfaces thoroughly and 2) whack the velcro with a hammer to set the contact adhesive.