Thanks so much for your extensive response! I really appreciate it.
One thing: "To resolve the problem, you are proposing to build different manipulative links, ones designed to trick search engines into removing the penalty."
No, not at all! I just meant that over time, the natural links they acquire will not have exact match anchor text, so once they have more links without it than with it, will it be enough to crowd it out.
I have looked up all the links to the site and gone to those sites one by one and attempted to contact them. 90+ percent didn't have contact information. Out of those 90+ percent, 90+ percent of those had a private whois listing. That's why I said the removal of the bad links is never going to happen.
It's a shame because the reason the client hired that shady company to begin with is because he didn't want me to spend time building links. He's never going to consent to my spending my time in an excessive campaign to remove them.
I guess there's nothing more to say.