EN este caso deberias usar un servicio de DNS personalizados, es decir, puedes hallarlos en
www.cdmon.com te registras y agregas tu dominio ahí, luego cambias las nameservers a las de CDMON.
EN el panel de Cdmon especificas que el registro A (address) dirija a la IP de tu hosting nuevo, y los MX vallan al servidor actual.
Yo he hecho ese proceso muchas veces y relativamente es muy fácil.