This is exactly why I got out of SEO services. I always did quality, white hat, and ethical work and had a lot of great customers for a long time, and they started getting eaten up by these idiots. Basically the story would be:

1. I perform work for customer, they're satisfied. They would show improvement and start getting more traffic.

2. Some scam company company calls them and appeals to their sense of greed.

3. They tell me they're going with the new company who erases everything I did.

4. Six months or so later they call me back because things are worse and want me to fix it.

5. I refuse because now they're deep in black hat territory, and either deranked by Google or well on their way. Or they'd have some strange legal issues popping up from the crap the other company did.

So yeah, after a while I jumped out of the business. I know that isn't exactly relevant to your problem, but these companies are just complete scumbags in every sense of the word, and anything you can do to damage them, you should.

Call a lawyer, and protect your good name. Take a chunk out of the bad guys.