[exim] Troubleshoot callout cache not working

As per an earlier post to this ML about slow email sending, the
problem was narrowed down to callout verifications on recipients: exim
was slowly verifying one recipient after another, locking down the
user's email program for literally hours for legit emails.

This doesn't seem to make any sense and after more testing, it seems
that exim is not caching any previous callout verification results.
When sending to a recipient the first time, it takes about 20 seconds
to complete the verification, sending a second email still takes the
same amount of time to do verification.

In debug mode, exim says there is no domain/address found in cache
despite sending to the same recipient twice in a row.
3714 opened hints database /var/spool/exim/db/callout: flags=O_RDWR
3714 dbfn_read: key=gmail.com
3714 callout cache: no domain record found for gmail.com
3714 dbfn_read: key=centos.admin@???/<test@???>
3714 callout cache: no address record found for
centos.admin@???/<test@???>

I've deleted the /var/spool/exim/db/callout file in case it was
corrupted and saw that it was recreated and updated as emails are
sent. Yet exim does not appear to be able to find any matches in it.

What could be the problem here?