Eventually I find a portal from MS to do exactly that: Appeal. I tried to use the portal but I got an error "event service error" - or something similar. Portal not working. I say "what the heck - I ll try later". I do try later, same outcome. Several times. For days. I google the error, I find several threads on redit since years complaining that the portal doesn't work giving this exact error. Since years. I keep trying nevertheless to respond to the email and go through the portal again for days. Nothing. I try the following: I signup for azure, it asks me for an email address, I say I have none and guides me to sign up to outlook. Outlook asks me for a backup email address, I provide my email address from the blocked server.
I then try to respond again to the original email that outlook has been rejecting - WORKS. Summary again: MS blocks email my mail server for not fulfilling requirements that it actually fulfills. MS portal to object, doesn't work since years. I create an outlook email and set self-hosted mail address as "backup" - my server gets unblocked.
Fun fact: I received "on-boarding" emails from MS Azure to my new MS Outlook account. MS Outlook classified them as "Junk".
Does this qualify as a "serious mail provider"?
--updated wording.