Your frustration is completely understandable; I have some of the same issues with some of my clients. Of course, I cannot tell you what you should tell your clients, though I can share with you what I tell mine.
I tell them the truth, irrespective of whether or not it will "fly". To my way of thinking, to tell them anything else is to do them a disservice. I would be remiss if I failed to point out to my clients that, in this day and age, for a business to "live and die by prompt communication via email" is a fundemental problem with their business model that should be addressed much sooner rather than later.
I say that because, the net is changing and, while in the past we have enjoyed highly reliable and often near immediate delivery of email, the whole email experience may well be going the way of usenet; because of spam, bandwidth load, signal-to-noise ratio, etc. it has become problematic to rely upon it for timely or "mission critical" communication. While in the (recent) past this was not the case (and in most circumstances still is not the case), we should realize that if it "absolutely, positively has to be there" by a particular time, email is often no longer a reasonably robust way to accomplish that in a busness environment.
For all of my clients, email is still useful and the overwhelming majority of email sent, and received, is delivered without incident and in relatively rapid manner. For the other problem email, whether or not we "like" it, there is no way to "make" any mail server "accept" any piece of email; the administrators of each server can accept, or reject, any mail they choose. Issues of contractural obligation to process mail by an ISP or mail service are generally made moot by the Terms of Service or Acceptable Use Policy, which give the service provider these "rights."
If the users' market, the customers who are having their mail blocked by their service providers, is not able to prevail with the management of their services, and absent any government intervention (the whole "net neutrality" issue is a much bigger, and more complicated subject - though this is related) I'm pretty sure this situation will not get better in the near and foreseeable future.
What to do? I'm not sure what is best, or what will work best for you, or your clients, but, in addition to (or instead of) educating your clients regarding the realities of email communications' present shortcomings and developing alternate business processes to account for these, you could throw money at it by maintaing your own static IP addressed mail server which you somehow keep off all the blocklists, and use that for your mail service. You could also change to a dedicated email provider, and hope they have less issues (though I really don't think that is likely to be of much help).
We are also starting to see some corporate email environments starting to "reject" mail from dynamically assigned "consumer based" IP addresses. They don't want their mail servers used by their employees, at work, to exchange email with "friends and buddies", to introduce virii into their network, and/or receive huge amounts of "Pass this letter on" or "Fwd: Great Joke/Video/Jpeg/etc" garbage that makes up such a hugh part of many "email connected" employees' traffic. I'm not saying it's "right", just that it is happening.
For most of my clients, the costs and complications of all that has led to them deciding, upon understanding the nature of the problem and the alternatives, to encourage those relatively few associates impacted by these blocks to arrange for an alternate/additional email provider (easy enough to do) and/or utilize alternate communications methodologies (phone, fax, mail, Fed Ex, etc.). The alternative methods to facilitate a particular issue are myriad, and can include online document repositories (call the client, have them download/upload the file), P2P networking, IM/IRC technologies, RSS, VPN, etc. Granted, none of this is as "convenient" as email the way we are used to using (abusing?) it, but it does provide alternatives. I mean, really, how did we get to the point where we are moving multi-megabytes of media files and documents via email attachments anyway? Email was never designed for the way it is now being generally used, but I digress.
Why? While I would love for this to be true, until the "blocking" entities find an economic incentive to change, why should they not limit their bandwidth/processing loads by such activity? I don't expect them to change without being "forced" to change. One of the things that could provide such an incentive would be a "revolt" and "exodus" from their servce by impacted users. Another might be strong net-neutrality legislation that would penalize such "packet discrimination" (not that I am arguing for that at this point!). I'm sure there are others. I certainly don't think that implementing convoluted "forward around" operations and wasteful "duping" of mail through various addresses to find one that "works" for every user (adding considerly to congestion in the pipes) helps as much as it hurts; while it might ultimately get a given piece of email through, it just magnifies the problem in the long run as it increases the "noise to signal" ratio of the email medium (as if it is not high enough already).
I'm sure we are only seeing the beginning of this, and I don't think it is going to get better anytime soon. To me, it is more useful to point my clients to alternate ways of dealing with the issue, than it is to "rail" against the provider of a shared email server (that I elected to use) because they were victimized by heavy-handed mail administrators. There is nothing "unique" about Dreamhost having servers being blocked by "the AOLs, Comcasts, etc.... (and).. domains using various databases and spam services" ; these same databases and spam services routinely block many providers.
Until this whole issue starts to come "full circle", if it does at all, the best any provider can do , including Dreamhost, is to carefully monitor their servers to prevent them being used by spammers (which I am convinced Dreamhost does very well), eliminate or tune processes as is reasonable to avoid the "worst" of the blocking (control certain forwarding circumstances, email volume limits, etc - while recognizing that you ultimately can not gurantee that someone will not block you in spite of your best efforts!) and educate their users as to where to complain - those implementing the blocks are the ones impacting "our" clients who use them.
That said, there is only so much we can "take on ourselves" as consultants and advisors to our clients. If/since they have chosen to have their email service provided by, or continue to choose, a service that filters so agressively they can can no longer reliably receive mail they desire, there is no reasonable way for us to sheild them from the effects of that decision.
Other than explaining what is happening, and why, and using our business and technical expertise to suggest alternatives, there is little more we can do. Ultimately, the situation is mitigated, or not, by their business decisions.