Thanks for all of the input. I had the talk with our email marketing company and presented all of the data that I collected about their mail servers. They're said that going to police spammers more effectively, and they know that I'm watching.
I did ask about the impact of blacklisting. They said that a SpamHaus blacklisting has the biggest impact. Deliverability can drop from 95% to 35%. A SpamCop blacklisting can reduce deliverability from 95% to 75%.
This morning I remembered another resource I used a while ago: http://www.senderscore.org which provides free mail server reputation statistics which give a good basic overview. They also have a more advanced paid service, but the free information give a lot of deliverability information.
According to senderbase.org, some of the vendor's servers have a very good reputation, and are running campaign from very large organizations. Some servers have a very low reputation. Apparently those servers are for customers with "issues."
By reading the comments here, collecting data from mxtoolbox.com blacklist monitors I set up, spamcop.net statistics, senderbase.org's list of the vendor's servers and senderscore.org's reputation scores, I had the information needed to get their attention.
Thanks for everybody's input.