[TriLUG] linux mail servers, RBLs, relays, etc.

[Dewey Hylton via TriLUG]

This isn't really a linux question, though I believe it is not strictly off-topic because it at least involves linux systems ...

I manage multiple linux-based mail servers for different customers. Most run Zimbra, but some are running opensmtpd (which I am liking more and more as time wears on). The problem I am running into is with the various RBLs ... and not my usage of them, either. Lots of folks out there leverage the RBLs to determine from what addresses they will accept smtp connections. In more than one instance now I have found outbound mail being blocked due to inclusion in one or more RBL. The pesky part of this is that the RBL listed an entire network based on one or more addresses which are not mine. So I'm being blocked thanks to someone with a similar address. Which means I'm being blocked for no fault of my own. Folks like Spamhaus are basically unresponsive (and when they respond they are unapologetic). I have moved networks multiple times in order to get around this. And that does work - at least for a time. But it is a huge pain in the backside. So now I'm thinking about changing tactics.

I have considered spinning up a low cost vm and running my own relay (most likely opensmtpd), as moving THAT around would be a LOT easier than moving an entire zimbra instance in some cases.

I have also considered a commercial solution. I know that companies provide mail relays as a service, and I'm hoping I can find one which protects their reputation enough that they stay off the RBLs. Can anyone here make a recommendation for one or more of these services?

Or is there perhaps a better way to tackle this?