Prior vendor holding domain hostage. Need Web Development and SEO guidance

We are an IT company that's picked up a new client unhappy with their current vendor.  Nothing new there but unfortunately their previous vendor put their domain in there name and is wanting to sell it back to the company.  The company initially purchased the domain thru their IT vendor and had no reason to believe their IT vendor wasn't acting in good faith.  The domain is the clients full business name and therefor would not be of any value to anyone else.  They are basically holding it for ransom.  We have setup a similar domain name and rebuilt their website.

Now with all that said, down to my question.  What can be done to get some of the traffic and various search engine's "attention" from their old site to the new one when we don't have access to the old site?  With their old site being the full company name and the fact that its been around a while at a minimum it has some organic advantages.  OK Guru's what tips, tricks, anything?  

We also have some concerns as to what these guys may do with the previous domain.  Legal action is of course an option but that can get very expensive and the attorneys are the only one's guaranteed to win.  This other vendor really needs to be taught a lesson and I feel strongly that karma will see to that.

Could really use some guidance here beyond the obvious "they should have....."   Doesn't matter.  This is where we are today.