Repasando el log de los mensajes de error, aparecía un mensaje que decía lo siguiente:

554 Your access to this mail system has been rejected due to the sending MTA's poor reputation. If you believe that this failure is in error, please contact the intended recipient via alternate means.

Mosqueado, me puse a investigar el motivo de tales errores, 

1) La primera gran ayuda me la proporcionó la siguiente web:

http://mxtoolbox.com/SuperTool.aspx?action=blacklist%3a<ip>

http://mxtoolbox.com/SuperTool.aspx?action=blacklist%3a80.80.80.80

Esta página te hace un escaneo de la IP del servidor SMTP, y verifica si la IP en cuestión aparece en la lista negra de entre cientos de blacklists conocidos. 

Si por algún casual tu servidor SMTP apareciera en alguno de los blacklists, mxtoolbox te lo notificaría, y te mostraría el link para que puedas acudir al blacklist en cuestion, pudiendo en cada caso eliminar el registro siguiendo las instrucciones. De esta forma, conseguirías eliminar la "mala reputación" que se ha generado con tu IP del servidor SMTP. 

Mxtoolbox te remite a una serie de páginas, como por ejemplo, las siguientes:

http://psky.me/check/

http://www.kloth.net/services/dnsbl.php

http://zy0.de/