I have had the exact same problem from the 19/10/2009, mail sent with php mail() got frozen with the same error in the logs.
I have recompiled exim from source but no luck.
I have followed the KB article with the tls modification in exim.con, no luck either.
The only solution is to switch to php-cli...
Strange.
(nothing was changed on the server, maybe a few users where added)