I found out this error in /var/log/exim_mainlog. When trying to fix the Exim database using /scripts/exim_tidydb, the same error occurred:

$ tail -f /var/log/exim_mainlog 2011-09-08 10:08:13 1R1cV2-0003Yq-J2 Berkeley DB error: page 40: illegal page type or format 2011-09-08 10:08:13 1R1cV2-0003Yq-J2 Berkeley DB error: PANIC: Invalid argument 2011-09-08 10:08:13 1R1cV2-0003Yq-J2 Berkeley DB error: fatal region error detected; [...]