MS schickt doch normalerweise eine Ablehungsmail („Blocklist“, etc) und wenn ich es richtig verstanden habe existiert das gleiche Problem mit Web.de.
Bei mir war es auch so, dass irgendwann die Mails vom Mailserver von MS angenommen wurden erfolgreich aber dann nicht zum Empfänger weitergeleitet wurden (auch nicht im Spam Ordner). Also wenn der Mailserver die Mail annimmt heißt das noch nicht, dass diese auch ankommen. Die Mails werden dann einfach ohne Benachrichtigung verworfen.
Bei mir war es damals so, dass ich auf Mails die ich von hotmail etc. bekam antworten konnte und diese dann erfolgreich auch beim Empfänger ankamen aber keine neuen Mails dorthin versenden konnte