[exim] Valid working host "failing for a long time"

Hi folks,

I am having a little issue which I am struggling to pin down.

Essentially my copy of exim has the followind router and transport:

#####Router Begin
static_route:
driver = manualroute
transport = remote_smtp_smart
route_data = ${lookup{$domain}lsearch{/etc/staticroutes}}
#####Router End
#####Transport
remote_smtp_smart:
driver = smtp
hosts_avoid_tls=*
port = 25
delay_after_cutoff = false
hosts = ${lookup{$domain}lsearch{/etc/staticroutes}}
hosts_override
#####Transport End

I also have the following ACL to call forward and validate user accounts 
before accepting mail:
#####ACL Start
   warn
     condition = ${if eq 
{1}{${lookup{$domain}lsearch{/etc/staticroutes}{1}{0}}}}
     require verify = recipient/callout=30s,defer_ok,use_sender
#####ACL End

/etc/staticroutes contains a list of entries such as:
domain.tld: 1.1.1.1

By and large this works fine, however there is one scenario where it
doesn't.

I have two customers who are both having inbound mail routed by the
staticroutes file to their in house Exchange server. Both customers also
use this instance of Exim as a smart host for their outbound Exchange.

Most of the time this works without issue but over the last month three
message have bounced immediately.

An example of the error is:

2011-08-22 13:18:16 1QvTSJ-0000hJ-Rx ** sender@???
<sender@???> R=static_route T=remote_smtp_smart: all hosts have
been failing for a long time and were last tried after this message arrived

This is quite clearly incorrect as within minutes either side messages
have been going through and there are no failures for the recipient at all.

To make things more confusing, the recipient has two domains on the go.
The three afftected messages all have the same sender address and have
two recipient addresses, one on each of the different domains that the
recipient recieves mail for. This is not the cause of the failure as
plenty of other messages go through from this sender to these recipients
without issue.

The in house Exchange server does not record any connection attempts in
its log files for the failed message.

The only other common thread is that all three messages either have
"Ladies Day" or "Ladies day" somewhere in the subject. No spam filtering
is in place after Exim that would be blocking this though.

I've run out of things to check - its not the Exim db going screwy
because these three messages are the only ones to fail with that error
in the past month.

What scenarios could cause Exim to return that error when the hosts
clearly have not been failing?