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

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.