Why does Exim bounce messages without even attempting delivery, giving the error retry time not reached for any host after a long failure period?

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 behaviour by unsetting the delay_after_cutoff option on the smtp transport. Then Exim will try most messages for those hosts once before giving up.

---