Sending email to Outlook, Hotmail, or Live results in: Please contact your Internet service provider since part of their network is on our block list (S3150)

Symptoms

You may receive the following message or see the following error in /var/log/exim_mainlog when sending an email to an @outlook, @hotmail, or @live address:

550 5.7.1 Unfortunately, messages from [$IP_ADDRESS] weren't sent. Please contact your Internet service provider since part of their network is on our block list (S3150). You can also refer your provider to http://mail.live.com/mail/troubleshooting.aspx#errors.

Description 

This error is returned when your mail server's primary public IP or an account's dedicated IP was found on the Outlook, Hotmail, and Live block list.

Workaround

To resolve this issue, you may first want to contact your server administrator or hosting provider, depending on the content of the received error. However, Microsoft will allow you to report mail delivery issues here.

You may also find our tutorial on "How do I check if my mail server is blacklisted?" helpful for more information.