You may remember that Microsoft domains (hotmail.com, outlook.com, live.com, and msn.com) were refusing all e-mail coming from my server. This is not as deadly as Gmail refusing to talk to you (as Gmail currently hosts about 50% of my contacts), but it’s still a pretty big deal.
Their servers would always reject my e-mail with this error:
2017-06-10 18:48:29 1dJlQy-0007SD-Fk ** firstname.lastname@example.org R=dnslookup T=remote_smtp X=TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256 DN="CN=*.hotmail.com": SMTP error from remote mail server after MAIL FROM:<email@example.com> SIZE=1814: host mx1.hotmail.com [126.96.36.199]: 550 SC-001 (SNT004-MC1F14) Unfortunately, messages from 188.8.131.52 weren't sent. Please contact your Internet service provider since part of their network is on our block list. You can also refer your provider to http://mail.live.com/mail/troubleshooting.aspx#errors.
Setting up DKIM on top of SPF that I already had did not help.
I finally ran into an explanation: Microsoft basically refuses e-mail coming from any new server. I think I’d been sending e-mail from that IP for a while, but apparently that wasn’t enough. The article points to a secret form on Microsoft’s support Web site, which lets you beg them to consider de-blacklisting your IP address. Apparently it works, so I can finally send e-mail to the 10% or so of my friends who are hosted by them.
I guess the next step is for Microsoft, Gmail and the couple of very large e-mail providers to just stop talking to any small server.