Interestingly, I've not had a problem delivering directly to those (except the time I switched to an IP block with a bad rep and couldn't deliver anything anywhere directly at all); it's just the ones on the list above that don't like me.

Mysterious and ineffable are the ways of Microsoft.

(note that their MX record is usually a *.protection.outlook.com entry regardless of the custom domain, so I'd use that to bootstrap a rule if I had a more general problem with Microsoft)