Of course it's going to hurt the other company and its employees, but think about how it's going to affect the submitter's company and small group of employees if they don't get paid for their work. It's a bad situation all around, but it's not the submitter's fault that these people have a employer who doesn't pay bills and he shouldn't have to suffer because of it.
I would probably talk to a lawyer first. For minimal fees you could have a few nastygrams sent out and the threat of a lawsuit might do the trick. If that doesn't work selling the debt to a collection agency for cents on the dollar might be the most cost effective solution.
[edit] Or you could get creative as boredguy8 suggests. I think it's a fantastic idea. It may or may not work, but it doesn't cost much and there's no PR fallout.
I don't know you, but you might be surprised how big an issue this is; back in the '90s, I was a key employee at a regional ISPs, and the deadbeat problem was significant.
The standard answer to this problem seems to be having a lawyer draft a letter (hundreds of dollars) threatening a civil suit, and then actually taking the deadbeat to court. If you think a stern letter will get someone to cough up, this is a fine route to take. If you think it'll require an actual court case, forget it. Business civil suits can take years just to get into a courtroom; if your opponent hires their own lawyer, your odds of winning aren't awesome compared to the investment you'll have to make with your counsel; in the end, if your debtor simply goes out of business, you end up with nothing even if you win.
What I'm getting at is that using a debt collection agency is an exceptionally nasty way to recover money. There are other avenues to explore, one of which was suggested by boredguy8 and another by tjic.
Note also: a good corporate collections agency might know tricks you wouldn't think of to spur repayment. For instance, you can ding people's D&B reports with collections issues (who knew?), which can cause problems for some companies with their other B2B transactions.
Some unrelated case-in-point: I'll pay parking tickets in jurisdictions where they're handled by collections. I won't bother paying parking tickets elsewhere, even when they have hard-and-fast "3 tickets and then we boot you" rules. The collections agency is just a bigger headache than getting a boot off.
"The delinquency letter you send out to deadbeat clients that says you work with XXX debt collection agency to recover fees is likely to get a better response rate than the one that says you'll "pursue all options"."
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.
First, collection agents are threatening and scary. Their presence will affect both the debtor company and its staff.
Second, by selling your debt to a collection agency, you usually give them the right to sell it to other - perhaps more menacing - organisations.
Third, collection agencies primarily work by first sending scary letters, then visiting the debtor in person, then confiscating things of value. None of these are efficient: the debtor loses far more than they owe, and you don't get all your money back.