Relaying email via Office 365 suddenly stopped working. Relayed emails were sent from a Windows 2012 Server using a simple PowerShell script. After logging in to the server and running the PowerShell script in an interactive mode following error was displayed:
Exception calling "Send" with "1" argument(s): "Mailbox unavailable. The server response was: 5.7.1 Service unavailable, Client host [126.96.36.199] blocked using Spamhaus. To request removal from this list see http://www.spamhaus.org/lookup.lasso
First of all I went to https://www.spamhaus.org/lookup and did a check on the affected IP address. Following result was returned:
This shows that IP address is on Spamhaus PBL (Policy Block List). This list is not a blacklist and doesn't mean that IP address was used for abuse or spamming. It simply indicates that IP is probably a dynamic or static residential IP address that normally shouldn't need to send emails directly. In this case this actually wasn't the case, the IP address was static and was provided via a business FTTC (VDSL) service.
It's was pretty easy to remove the IP address from PBL list. All you have to do is fill a simple form on https://www.spamhaus.org/pbl/removal and click a confirmation link in an email sent to you. I took about 45 minutes after submitting the form for Office 365 to start accepting emails relayed from this IP address.
Office 365 / Exchange Online