Micha, danke für den Test und auch vielen Dank an Klaus - der Wireshark Hinweis hat mich auf den richtigen Weg gebracht. In Wireshark habe ich gesehen, dass der EHLO/HELO Befehl diesen Fehler zurückliefert. Ich dachte immer das bei HELO der Benutzername oder die Emailadresse rein muss - extern hat das auch immer geklappt. Exchange verlangt an dieser Stelle aber den Domainnamen.
Mit dem Domainnamen als HELO funktioniert der Mailversand über den internen Exchange bei mir