"Es lag an einem eigenen MX-Eintrag mit niedriger* Priorität."
Das kann ich nur bestätigen. Sobald nur noch NC Mailserver drin standen, ging es sofort.
Da ich danach auch ewig gesucht habe, schicke ich das nochmal FETT nach. 
*Niedriger ist hier wie gewohnt gemein, also 1 hoch 100 niedrig. Warum auch immer das stört(e).