A few things come to mind:
1. Do you have MailScanner installed? Is it running?
2. Do you have queue_only set in /etc/exim.conf (and aren't using MailScanner), if so, remove it and restart
3. What do you have specified at the bottom of your /etc/exim.conf for the retry intervals? By default it is set to:
Code:
* * F,2h,15m; G,16h,1h,1.5; F,4d,8h
4. Does your server always run at a high load average? If so, do you have deliver_queue_load_max set in exim.conf? If the value for deliver_queue_load_max is lower than your load average then it probably will never run.