Evidentemente, lo primero es comprobar que el cliente de correo está bien configurado.
Si se realiza un cambio del servidor de correo electrónico, pueden aparecer problemas con el cliente de correo Microsoft Outlook a la hora de enviar o recibir correos electrónicos.
Cuando se configura el correo en el Outlook, éste guarda en una pequeña caché la IP del servidor para no tener que comprobarla cada vez que envías y recibes correos.
Al cambiar el hosting de servidor de correo, se ha modificado la ip. Como el Outlook no refresca la información al instante, es posible que estuviese intentando acceder al servidor viejo para enviar o recibir correos.
Si te ocurre, podrás entrar a la consola de comandos de windows y ejecutar este comando: ipconfig /flushdns
De este modo volverá a buscar la ip del servidor para conectarse a él.