I would consider contacting the BBB and possibly small claims court about these folks, although I can't say I believe much would come of it. It's a shame that we don't have any better method of recourse when a business fails to provide the service that was promised, but unfortunately it seems to happen all the time. The BBB should have the power to revoke and or deny business licenses and your record should follow you no matter what state you apply in. Otherwise, what good are they?