Emails sent to hotmail / outlook rejected due to ip address on block list

[#1]

Sending emails to various email addresses (normally hotmail.com and outlook.com but other addresses too) result in the following type of error:

Delivery has failed to these recipients or groups:

xxx_xxx@hotmail.com (addressee removed as domain is important rather than recipient)
A problem occurred while delivering your message to this email address. Try sending your message again. If the problem continues, please contact your email admin.

The following organization rejected your message: hotmail-com.olc.protection.outlook.com.

Diagnostic information for administrators:

Generating server: utm.bhatt-consulting.com

xxx_xxx@hotmail.com
hotmail-com.olc.protection.outlook.com
Remote Server returned '554 5.0.0 <hotmail-com.olc.protection.outlook.com #5.0.0 smtp; 550 5.7.1 Unfortunately, messages from [212.159.69.xx] 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. [DM6NAM12FT049.eop-nam12.prod.protection.outlook.com]>'

Checking against MXToolbox shows I am not on any blacklists so I am assuming the problem is due to the subnet range assigned to me that has a bad reputation.

blacklist:212.159.69.xx

Checking 212.159.69.xx against 83 known blacklists...
Listed 0 times with 5 timeouts

Please advise how to resolve. 

[#2]

Hello @cbhatt

Thanks a lot for reaching out and I'm sorry to hear about the problems that you're having when trying to send emails. This is likely because the IP address that the emails are being sent from has a bad reputation on Cloudmark's end.

Can you please send me a PM with the full header on the email you sent, as well as the one on the bounce back email?

[#3]

Thanks Adam. PM sent.

Kind regards,

Chris