Und bei mir war es eine Router-Einstellung: "Liste der sicheren Email-Server".
Erst als ich die nach ewigem Herumsuchen gefunden und entsprechend editiert hatte, ging es plötzlich.
Allerdings hab ich einen Telekom Router, keine Fritzbox. Aber vielleicht gibt es ja da auch irgendwelche Sicherheitseinstellungen, die Dein neues Postfach aussperren.