Esto puede ocurrir debido a que aun no se hacen efectivos los cambios de los registros MX en el nuevo servidor de correo que has activado.
Si es en Gmail el proceso toma entre 1 a 24 horas normalmente.
Si es en Live Mail el proceso toma entre 1 a 48 horas normalmente.
Estos tiempos pueden variar por muchos factores.
Revisa tambien, que has apuntado correctamente la direccion del nuevo registro MX.