The IP address of our mail server was recently blacklisted by MSN/Hotmail. When I went through their steps for delisting, it was denied based on "reputation". AFAIK, we have not had a spam problem for several months. When we did it was due to a few accounts having been successfully phished. Since then our customers have been far more savvy and I have not seen the problem. I manually delisted us from all the known BLs back then and all has been ok. A current multi DNSBL lookup only shows 3 out of a couple hundred BLs listing us. You may be familiar with the ones that did (blackholes.five-ten-sg.com for example). No major, reputable, widely used DNSBL lists the IP. I have been doing this for 16 years. It has always been SOP to provide an offending email, with full headers to the complaint recipient, if not in advance of such blacklisting, then at least upon request. They sure require it of me when I report abuse of their servers. They flat out refuse to do this, claiming they have no access to this. I had this same issue with Cloudmark's BL a couple of months ago (which Comcast and other major providers use), so I suspect this is some kind of outsourced blacklist that does a poor job of updating their listings or one of my regular customers is sending out emails that are being incorrectly reported as spam. I have seen the latter happen several times with other servers I've worked with that auto generate legitimate emails of reports that customers pay for, but aggressive filters such as AOL's auto-report as spam (to be fair, AOL is excellent at resolving these). We do have SPF records for our main domains, but no DKIM or other whitelisting/authentication mechanisms. Is this sort of thing going to be widely required?