I’ve had similar experiences trying to send mail to Microsoft-hosted email addresses. My current “solution” is to send all outgoing mail directly from my VPS-hosted Mailu server… EXCEPT for Microsoft-destined mail. For those messages, they get transparently relayed from Postfix to a third-party email sending service that Microsoft apparently trusts.
The upshot is I can still use my own Postfix daemon for all mail sent to sane (non-Microsoft) providers.