"First time?"
It's not months it's years.
Anecdotal. I've self-hosted for many years but didn't run into these issues with O365 until this year. But not surprised to hear it.
They used to just drop all messages from domains not on their whitelist and to get whitelisted you needed to have a Microsoft account and open a support ticket.