The load on a server has nothing to do with exim freezing or queueing mail, really, unless it\'s so high that exim has to wait its turn for a chance to get part of the processor time - but that would have to be pretty severe. We have had a single case of mail being delayed for hours because the remote gateway was closing the connection too quickly (right after the RCPT TO header, in fact), and there\'s not a lot that we can do about that except contact the postmaster of the recipient system to ask them what\'s going on. We haven\'t really had any problems with exim - or at least none more than we have with say, sendmail. Every MTA has its own issues, but it\'s hard to lay this problem on exim without seeing something that would indicate exim is rejecting or not even making the attempt to deliver the mail right off the bat.
Things I\'d check (that I did check, after finding that single domain with the delay issue):
Do you actually have mail queued up for the domain that is not receiving the mail? Or is the mail going out, according to the logs? If the former, did you take a look at the message in /var/spool/exim/msglog for that particular message id to see what exim says the problem is (usually the first line, since the remainder will be the standard \'retry time not reached\' stuff)? If the latter, then it doesn\'t really have anything to do with exim at all - if it\'s making it off your server, you really can\'t do anything about the routing once it leaves.
If you do have something in /var/spool/exim/msglog, what does it say for those messages? Have you attempted delivery to the problematic address while watching to log roll? What results are posted to the log when you try? Can you post a snip from the log (names obscured to protect the innocent, of course
When you send mail through webmail on one of the affected domains, is the behavior different? When you send mail to the account on the system from somewhere else, is the mail likewise delayed? How about from the domain to which they are trying to send mail and finding it delayed? If it\'s delayed both ways, it isn\'t the server, it\'s the routing.
There\'s more, but that\'s a place to start. Believe me, although my initial message may have seemed harsh since I left off the little smiley after the Psychic Network piece, more information is really needed to properly troubleshoot things like this.