Try

Sending a mail from command line with:

echo "Test" | mail -s Testmail foo.bar@gmail.com

or

exim -bt recipient@address

to see what Exim thinks should be done with a particular address, and add -d to the command-line to get more debugging information (but beware that there can be a lot to pick through).

Succesful logs would have something like

2011-01-01 20:45:24 1PZ7OG-0001Vp-Rx <= root@gustav U=root P=local S=360
2011-01-01 20:45:26 1PZ7OG-0001Vp-Rx => foo.bar@gmail.com R=dnslookup T=remote_smtp H=gmail-smtp-in.l.google.com [209.85.229.27] X=TLS1.0:RSA_ARCFOUR_MD5:16 DN="C=US,ST=California,L=Mountain View,O=Google Inc,CN=mx.google.com"
2011-01-01 20:45:26 1PZ7OG-0001Vp-Rx Completed

Unsuccessful logs would have something like:

2011-01-01 20:50:08 1PZ7Sq-0001X9-L4 <= <> R=1PZ7Sq-0001X7-Jo U=Debian-exim P=local S=1780
2011-01-01 20:50:11 1PZ7Sq-0001X9-L4 => newsletter@foo.bar R=dnslookup T=remote_smtp H=mx1.emailsrvr.com [98.129.184.3] X=TLS1.0:RSA_AES_256_CBC_SHA1:32 DN="C=US,O=mx1.emailsrvr.com,OU=GT21850092,OU=See www.geotrust.com/resources/cps (c)08,OU=Domain Control Validated - QuickSSL(R),CN=mx1.emailsrvr.com"
2011-01-01 20:50:11 1PZ7Sq-0001X9-L4 Completed

The R= is saying that this item is a bounce and the message-id given in the R= part is the original message-id which failed. You'll need to look at the log-entry for that to see what recipient address was generated and why it failed.