I filled the form, was requested documentation from my ISP on the IP address.
I asked my VPS hosting company (since they provide the public IP and therefore act as ISP) and they proactively reached out to Microsoft, who lifted the restriction after that.
So since then no delivery issues. YMMV.
If you intend to host this from your residential address, it can be a good idea to tunnel external traffic over VPN through a VPS or similar. Not only for privacy reasons, but also to get around ISP blocks and IP banlists. I don't know how flexible maddy is, but in postfix in case the above scenario wouldn't be resolved, I could have set to use mailgun/mailroute for MS domains only and relay like normally for others.
But like I mentioned, what eventually resolved it was the ISP contacting them.
I have had a number of bumps:
1. In exchanging emails with someone with a custom domain, I found there SPF record was broken and thus my server was rejecting their emails. I've weakened my policy and now their mail goes to my Junk, which I then manually move to my inbox because I'm lazy and don't want to set up a custom rule.
2. I wanted to subscribe to the Tarnsap mailing list, and had to decrease the minimum TLS level for outgoing mail to "none." Dr. Percival believes TLS on SMTP is "silly" (which, in the sense that all email is insecure, is true, but in the sense that email with modern security measures is better than nothing, is in itself a "silly" opinion).
3. I had some server downtime recently (https://figbert.com/posts/wrong-way-to-switch-server-os/) and couldn't receive emails, which sucked. But that was on me.
I highly recommend giving it a go!Our external auditors get all upset about it every single year, and every single year, I show them the RFC's and they then shutup about it for a year. If you feel strongly enough about it, try to get a RFC passed where SMTP requires TLS now.
Generally if you have a static IP and you don't go being all stupid with spam, it's not THAT difficult, but you do have to jump a few hoops and then occasionally play wackamole with their spam prevention junk for the month.
It seems to come in waves, like email will be fine for a few months and then 1 provider after another will be all upset about gosh knows what that day and you have to visit URL's and push a few buttons.
I've been to lazy to track it, and the various reasons for that particular day, but this has been my experience. A few times a year you have to go babysit SMTP so email can be delivered again.
We host and manage the SMTP server(s) ourselves(We currently run Postfix). If you outsource your email to Google, etc, then they have to babysit the email logs for URL's, not you.
Do they care? How would I know? =(
I have no idea why that helps (well, I could guess that some spam heuristic thinks plaintext email without an accompanying HTML envelope is more likely to be spam), but changing this took me from near-constant "your email went to spam" to no issues sending even things that actually look spammy (i.e. an email just containing a link that might be of interest to the recipient)