Hmm... if a thaw/retry works, then it almost seems related to this old guide:
http://help.directadmin.com/item.php?id=114
which refers to the file descriptor limit issue.
If the "live" process, like smtp or php mail()->exim are already at or over the FD limit, then it might fail..
Then it goes into the spool to be retried later... and the "later" exim process is not a child of "apache", so the FD limit might not apply.
Check:
/etc/init.d/exim
and right after the #!/bin/sh line, try adding:
also check your shell's current limit:
if it's showing 1024 and you restart exim, then exim's new FD limit might be 1024.
So adding the high value right in the exim boot script overrides whatever limit it's being given and tells the system that it needs more.
Anyway, that's just a guess, so see if that makes any difference for you.
John