Micro$oft is the devil. I assure you that you are not alone.
I recently created a SMTP relay product that I plan to market sometime in the future that will get around this inexpensively.
Another small business user that I was helping on Slack, desperately needed a solution, so due to that I created the service that I just mentioned. They have been using it for just over a month now with no issues.
I had investigated various SMTP mail relay providers and they all were rather unreliable utilizing their free tiers as they have so many people abuse the service. So due to this, using a free SMTP relay is just as bad if not worse than using none at all. To move to a paid service with most providers the cost starts at $50/month! That is simply out of reach for the majority of MiaB users.
Oh, and just an observation – I do not believe that other VPS providers are impacted by this as I am running and maintaining 3 other MiaB installs on VPS’s from other providers without this issue. I would venture a guess that DO’s IP range, or parts of it, are being blocked by M$.