Q:

Microsoft is blocking mail from entire netblock. ISP doesn't know what to do?

I recently moved a client from basic T1 service to a multi-site MPLS solution with same vendor. The ISP, XO Communications, provided a decade of stable service as a T1 provider. The process of moving to the MPLS was a bit rocky and involved an IP address reassignment.
Following the firewall, link balancer, Exchange, DNS and other necessary changes, we went live on the new lines.
Shortly after, outbound mail from the client's Exchange server began to bounce. SPF records, rDNS and other items were all correct. We weren't on any blacklists either. The bounced email appeared to all be related to Microsoft-protected domains: hotmail.com, live.com, msn.com, outlook.com
In the interim, I created a send-conenctor in Exchange to relay these domains through another Smart Host.
I ended up contacting Microsoft directly and was told that the new MPLS netblock was blocked. I was given no further explanation. Mail to other domains works fine. I put the onus on the customer to pursue this directly with the ISP, as the ISP shouldn't have portions of its IP space blocked by such a large mail host.
In the end, the has been escalated with the ISP, and after 5 months, their conclusion is that Microsoft won't budge and will continue blocking the IP addresses. The ISP has offered to provide a new net of IP addresses for us to use.

Is this normal?
What can be done about it?
Why can't a large ISP like XO sway Microsoft or even obtain a temporary clearance?
Is it reasonable for me to expect new internet service to be free of problems like this?

A:

It's not that unusual for large swathes of IP addresses to be blocked due to past or present problems with a particular provider or that particular netblock.
Microsoft can pretty much block whatever they like as an email service provider. Their responsibility to their customers means they have to balance the problems caused by having a block against the problems caused by not having the block in place. I'm not saying that they've made the right choice here, just that its a fairly normal thing for them to do. The question to be asking XO at this point is "why won't they budge?". No email service provider lists large blocks for fun, and if they're not removing that block that suggests they don't believe the issues with it are resolved.
As to what to do about it, the best option at this point might be to smarthost to a email provider such as mimecast or messagelabs.

