I have been having the same issue. After looking at the exim log (/var/log/exim4/mainlog) I tried enabling ipv6 on the wan interface. As soon as I did that, the emails started flowing, and all the ones stuck in the queue came in too. I hope it can help someone else. For what it's worth, I am using smtp.gmail.com:587 with auth for smtp.
I would like to see if this can get "fixed" though - I don't want to leave ipv6 enabled because I'm too busy/lazy to learn how to secure a box over the ipv6 vector.