I understand that you find collection agencies "scary" but at this point I've exhausted all other avenues. My responsibility is to my company, not their company and staff.
boredguy8 made an excellent suggestion of an alternative approach.
Boredguy8's suggestion seems odd to me, in that it's unlikely to work too often, and even if it does, the attitude of the other company in the OP is such that I would want nothing to do with them going forward.
Other people have made suggestions for alternatives: tptacek (small claims court), tjic (scary lawyer letter), boredguy8 (a social engineering approach).
Lawyer Letter: TJIC's suggestion is a very good one. However he's already sent them a copy of the legal contract the company signed, so it's possible this could likely be a waste a few hundred bucks of attorney fees. If he tried this, and they continued to ignore him, would a collections agency be a logical next step? If not, what would?
Social Engineering: Frankly it sounds like the new CEO isn't going to say "Oh you're going to fly here, man I better cut a check quick". So you're probably out a plane ticket a day of work.
The last thing a small business needs to do is to have a key person wrapped up for hours/day/weeks trying to recover money from a clearly uncooperative/belligerent person. They need to find the best balance of revenue versus time spent. After the threatening legal letter (which is sort of dick-ish I guess), I think a collections agency is the next logical step.