Esto ocurre cuando se ha intentado enviar en repetidas ocasiones hacia un destino y este por alguna razón falla.
Para ello hay que borrar la caché del exim:
exim_tidydb -t 10m /var/spool/exim retry
exim_tidydb -t 10m /var/spool/exim wait-remote_smtp
Fuente: http://rm-rf.es/exim-retry-time-not-reached-for-any-host-after-a-long-failure-period/