Es probable que después de algún tipo de bloqueo, configuración, blacklist, firewall sigamos sin poder enviar correos a ese dominio y nos diga:
all hosts for ‘midominio’ have been failing for a long time (and retry time not reached)
Exim guarda en cache las conexiones fallidas y las omite para ahorrar recursos en el servidor, para ello debemos realizar lo siguiente.
service exim stop
rm -fv /var/spool/exim/db/*
service exim start
con lo cual, nos cargamos la cache y deberías poder enviar sin problema a ese usuario.