En caso de encontrar este error en los logs de exim hay que conocer que son debidos a que el host al que hace referencia el error ha estado fallando gran cantidad de veces (normalmente 4 ó 5 días seguidos), y ha superado el límite de reintentos (retry).
En las FAQ de exim podéis ver la explicación:
This message means that all hosts to which the message could be sent have been failing for so long that the end of the retry period (typically 4 or 5 days) has been reached. In this situation, Exim still computes a next time to retry, but any messages that arrive in the meantime are bounced straight away. You can alter this behavior by unsetting the delay_after_cutoff option on the smtp transport. Then Exim will try most messages for those hosts once before giving up.»
A partir de este momento automáticamente exim rechazará enviar mensajes hacia dicho host. Esto queda guardado en la bd de exim. En caso de conocer que el problema con el servidor destino ha quedado resuelto, podemos vaciar esta base de datos para que exim vuelva a intentar enviar correos al mismo, para ello haced lo siguiente:
exim_tidydb -t 10m /var/spool/exim retry exim_tidydb -t 10m /var/spool/exim wait-remote_smtp
Ya deberíais poder enviar al host implicado sin problemas.