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.
_________________________
May I walk in beauty.