Si has cambiado los dns el outlook no vá conectar al webmail del antiguo alojamineto. Una solución cambia los dns del dominio al viejo host (la pagina aparecerá caida mientras haces esto) el outlook te tomará todo el correo que tienen las cuentas, una vez que lo tienes, vuelve a poner los dns del actual alojamiento al dominio y listo, si las cuentas de correo se llaman igual instantanamente va funcionar en el nuevo webmail el outlook con todos los mail dentro del outlook, no estarán en la bandeja de entrada del nuevo host, si quieres subirlo al bandeja nueva hay una opción para hacerlo que no recuerdo ahora donde está. Estará caida la página unos minutos, eso si.