Esta misma consulta la encontré
aquí y recibiste una respuesta, además de un valioso consejo.
Básicamente, no coinciden los servidores de nombre (DNS) que tienes asignados desde el panel de tu dominio, con lo que tienes configurado del lado del servidor. Esa fue la respuesta.
Y el consejo es muy válido, pues no sólo se supone que el proveedor de hosting que elegiste debería darte un soporte medianamente adecuado al menos, sino que además solamente ellos (además de ti, supongo) tienen acceso al servidor, a los registros (logs), de manera que podrían revisar qué está ocurriendo.
Y por último, nadie mejor que ellos conocerá el producto que te han vendido y qué incluye. Por ejemplo, a lo mejor te dan la posibilidad de usar sus DNS para el dominio que vas a hospedar en tu VPS, con lo cual ellos (y nadie más en este mundo) son los que podrían agregar el respectivo registro MX para que apunte hacia tu VPS.
Un saludo.
