Exim bounced back message “retry time not reached for any host after a long failure period”

Centos's solution:

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

If its still not working backup and remove all under /var/spool/exim/db folder

service exim stop
cp -rp /var/spool/exim/db /var/spool/exim/db_back
cd /var/spool/exim/db
rm -fv /var/spool/exim/db/*
service exim start
Read the rest