Exim is an one of the mail server and such error messages comes just because of corrupted exim db files and it can be fixed with the help of below steps:
Goto /var/spool/exim/db and delete files: retry , retry.lockfile , wait-remote_smtp, wait-remote_smtp.lockfile
/etc/init.d/exim restart
Also you maybe want to delete left over stuff under /var/spool/exim/input and /var/spool/exim/msglog for a better restart
