Furthermore, you need to pick a host that takes action when their IP addresses appear on blacklists. Microsoft, particularly, uses UCEPROTECT as a blacklist source, and that particular company will blacklist and entire ASN if they receive too much spam from a particular IP address block (that doesn't get resolved in time).
If I understand correctly though, I should have to set a reverse PTR record in the case of setting up my own mail server, right? And I should configure it on the mailserver's side, correct? That's not my case though, I'm just using a custom domain with the MX records pointing to the mail service that I'm using.
I'll just wait a few days cause the domain is new and I guess that's the reason outlook.com flags it.
They absolutely do not use that crap.