Das ist alles ein Schmerz mit denen. Ich habe letzten Monat 2 Server umgezogen, die Domains gibt es auch schon lange, Mails werden DKIM signiert, SPF gesetzt. Beide sind im 45.129.180.0/22, einer der beiden wird beim Versand an outlook.de etc, geblocked, jedoch nicht an irgendwelche O365-Tenants oder so.
Auf der Mailingliste, auf denen diese Probleme oftmals thematisiert werden, zeigt sich aber, dass das /22 nicht das einzige Netz ist, bei dem sich Microsoft so verhält: