Hi GG. I'm an owner and co-founder of two companies, one of them is specifically related cloud based Email Filtering, the other is related to Web and dedicated server hosting.
I won't mention them here but if you PM me I'll give you the website details.
Our web and dedicated server hosting systems use, as the outbound SMTP relay (ie. SMART Host), the services of our cloud based Email filtering service. The Email filtering service has inbuilt protection from spammers trying to use the service to send spam (for obvious reasons) and if any client uses our outbound relay and gets infected resulting in accidentally sending spam, the service manages that too (it can limit outbound emails per x minutes from SMTP floods etc).
One of the newer features we'll be introducing this weekend is the ability to "rotate" outbound IP's, so in the remote chance one of our outbound IP's get blacklisted, we can tell our service to stop using that IP and use another from a pool we assign, minimising any type of RBL outage for customers.
Due to the volume of outbound emails sent through the Email filtering servers, our service is recognised and trusted by the largest Email providers and RBL lists in the world ie. we should never be blocked by anyone from receiving emails from our servers. We also have formal reporting agreements with various RBL lists who accept our spam reports to block IP's, URI's, etc.
At the end of the day, all your problems will be solved if you use an outbound SMTP relay service that's dedicated and trusted, the tighter email security gets the more and more this will become the norm. It also goes without saying, it's always better to use an SMTP Relay than send directly from the server yourself.