Bounced Message “retry time not reached for any host after a long failure period”

It is likely due to an error with the server sending mail at their end. The Exim Retry Database has likely become corrupt and would need to be fixed before they could retry sending mail to your email address/domain.

cd /var/spool/exim/db
rm -f retry retry.lockfile
rm -f wait-remote_smtp wait-remote_smtp.lockfile
service exim restart

Or, use the following commands:
/usr/sbin/exim_tidydb -t 1d /var/spool/exim retry > /dev/null
/usr/sbin/exim_tidydb -t 1d /var/spool/exim reject > /dev/null
/usr/sbin/exim_tidydb -t 1d /var/spool/exim wait-remote_smtp > /dev/null
/scripts/courierup — force
/scripts/eximup –force