Wenn der Mailserver korrekt konfiguriert wäre, würde ich vermuten, dass der MX noch nicht überall geändert / propagiert ist.
Unverzichtbares Tool zur Mailkonfiganalyse: Network Tools: DNS,IP,Email (mxtoolbox.com)
Denke auch, dass entweder die DNS nicht richtig gesetzt sind oder die Änderungen noch nicht durch sind weltweit.