One of the ways to avoid this, in the US and I think Canada, ask for there Associated Locksmiths of America (ALOA) number. In the UK ask for their MLA (Master Locksmiths Association) info.
If they don’t have them, don’t expect them to know what they are doing.
Also don’t trust google maps or other street views to see if the company is legit, the NY Times has shown how easy to fake them (see my comment to Skeptic).
This site has good information on how to find a good locksmith too.
http://findalocksmith.com/search.aspx
