I even went as far as signing up for Azure, in the hopes that if I sent from a Microsoft IP it might not get blocked. But I didn't make it very far, every step of the way was like watching paint dry while the interface loaded or did something. Once I finally got the thing set up in order to send mail, the API was so molasses slow that it couldn't handle our mail throughput. Meaning it would take about 30 seconds to send each transactional email because of how slow their API is. Well that's only 2880 emails per day, that is not a reasonable send rate at all.
I have even lost customers over this mess, it's really hard to explain to them that they can't receive our email because of their provider and not us. Especially when Microsoft has the audacity to return: 250 OK Email Queued (but then not deliver it anyway!)
If anyone has any solutions to this mess I am all ears!