S.O.S Servidores de Correo

[cata522]

Compré un dominio y un hosting en una empresa x. Por ahora solo lo estoy
usando para correos corporativos y es allí donde he tenido mil inconvenientes.

Todos los correos que envío a desde las cuentas corporativas que creé me rebotan a las 24 o 72 horas con el siguiente
mensaje Error "Mail delivery failed: returning message to sender" ó
"554 This server requires PTR for unauthenticated connections". ó
"Warning: message 1THNwk-001sKn-15 delayed 72 hours"

Ya me he comunicado con el webmaster de mi servidor y me han hecho configurar el servidor de correo de salida
seleccionando la opción "Servidor requiere autenticación"
pero el error persiste y los correos siguen siendo devueltos y el servidor no me da más opciones.
Ya identifique que el problema no es en los servidores receptores de los correos, o direcciones mal escritas etc..

Es posible que haya algún conflicto si los correos son administrados desde USA y los servidores de las cuentas
de correo a las que envío los mails también son de USA y el hosting haya sido adquirido en colombia?

Es posible que simplemente mi proveedor de hosting tenga una muy mala plataforma, es decir esa empresa de servidor sea
muy mala?

Puedo trasladar mi dominio a otra empresa con otro servidor? Y cómo se hace este proceso?
Conoces alguna empresa que me recomiendes?

Algo más que pueda hacer al respecto..?