A bit harder - use of a telephone book would probably solve a fair portion of cases where they didn't just get straight in (assuming you paid with your own credit card and so they had your name).
But if you pay by credit card, that applies to any key copying service, online or not.
Old-fashioned key copying services don't necessarily have the opportunity to make their own copy of your key.
They could just sneakily make a picture of your key.