This happens when attempts to send to a destination have failed for some reason.
​
To fix this, you need to clear the exim cache:

exim_tidydb -t 10m /var/spool/exim retry
exim_tidydb -t 10m /var/spool/exim wait-remote_smtp
​
​
Source: http://rm-rf.es/exim-retry-time-not-reached-for-any-host-after-a-long-failure-period/