Yo tenía el mismo problema con mi empresa de hosting y con el programa de servidor de correo de argosoft (
www.argosoft.com) lo he solucionado, y la configuración es de ló más sencilla, así puedes enviar correos desde tus cuentas sin problemas.
Pruébalo a ver qué tal te va.