If you implement SPF / DKIM / DMARC / ADSP, force your customers to relay
Before we went SaaS with email we had lots of spam problems and we also went this route .. you must relay through us and authenticate .. postfix along with the dkim and policyd milters (and SPF in DNS). The policyd one would limit you to X messages in Y hours (per SASL credential), and we would override it for people that had a specific need. That was very effective at limiting the spam damage. I'm sure your needs are different as a commercial provider but we found that hardly anyone sends more than 100 messages a day, and 100 spammy messages isn't enough to get you in trouble, as long as it stops there. We have a /16 where most of our stuff lives and have moved things around a bit .. Spamhaus was pretty easy to deal with, as were the other major players (MS, Google, AOL, Yahoo) by just filling out their postmaster forms. Basically you just need to explain how you are fixing the problem and they usually answer you in less than 24hrs. The only IP addresses we have that I'd consider permanently tainted are the ones we've run TOR exit nodes on. We haven't run TOR in a couple years now but those IPs are still blacklisted so many places they are essentially unusable in any reliable capacity -- something to keep in mind while crafting your TOS. -Michael Holstein -Cleveland State University