Ich habe nun verschiedene Clients aus dem Firmennetz getestet und Clients außerhalb. Alle aus dem Firmennetz erhalten eine Antwort ohne Starttls, alle anderen mit.
Daher tippe ich aktuell auch auf die Firewall.
Die wird es sicher sein. Der Mailserver unterscheidet nicht nach Herkunft der Verbindung - der bietet allen SSL an. In großen Netzen ist es üblich, dass kein verschlüsselter (= nicht scanbarer) Traffic nach außen geht. Einfach mal mit den lokalen (zuständigen) Admins sprechen, ob eine "unverschlüsselte" Verbindung (bis zur Firewall) erlaubt ist, bzw. was die empfehlen würden.