So, hier nun - endlich - die Auflösung.
Die Namen der Postfächer waren in Groß statt der Kleinschreibung eingetragen worden. Also sollte es sein "postfach12345-name". Zum Beispiel "ws8930239-klaus". War aber "ws8930239-KLAUS". Damit funktionierte der Empfang, allerdings nicht der Versand!? Ich frage ich wie das möglich ist, dass der Empfang damit gewährleistet ist, der Versand aber nicht? In den FAQ des Webhosters habe ich nichts darüber gefunden. Auch als ich mit den Support telefonierte wurde ich darauf nicht angesprochen. Erst als wir die Daten zur Überprüfung in der Mail an den Support versendeten, fiel das den Supportern auf.