Cita: Pues ya está solucionado, hablé con Hostalia, me activaron el rdns para que resolviera la IP de mi VPS y todo arreglado, ya puedo enviar correos a las cuentas que antes no podía!
Desde siempre lo más aconsejable es contactar en primer lugar al proveedor, se obtiene una mejor y más rápida respuesta en la mayoría de los casos.