Problema Hosting y Correo

[ubicuo]

Hola. Espero que este post esté en el lugar correcto ya que no me gustaría que se perdiera el orden de este útil lugar.

Bueno, mi problema es el siguiente: contraté un servicio de correos a una empresa; me dijeron que comprara un dominio y así lo hice. Actualmente tengo 5 cuentas de correos con el mismo dominio y me las administra dicha empresa (filtrado, anti-spam, etc). Ahora bien, tengo un sitio web que me gustaría subir a un hosting que compré en otro sitio. Sin embargo, deseo que mi proveedor de correo siga administrando mis cuentas, pero al cambiar las DNS del dominio para usar mi hosting, el correo deja de funcionar. No recibe ni envía correos.

En el dominio estaba configurado como servidor primario y secundario el nombre y la ip de la empresa que me brinda el servicio de correo. Pero para usar mi nuevo hosting debo cambiar las DNS y ahí se produce el problema.

Ojalá puedan ayudarme y decirme qué tengo que configurar para seguir recibiendo y enviando correos normalmente.

Gracias.