Exchange Verteilt nicht alle Mails

Alles scheint ganz normal zu laufen, wird der Server allerdings neu gestartet, werden teilweise alte Mails (die das Alter seit dem letzten Neustart haben) an die einzelnen User versendet. Dies geschieht relativ wahllos, das heißt ich kann hier kein Schema erkennen (außer daß es alles externe Mails sind). Der Exchange scheint die Mails also irgendwie zurückzuhalten und erst nach einem Neustart zu versenden.
Die Mails werden nicht über POP abgerufen, sondern sie werden ihm direkt zugestellt über in Linuxgateway per SMTP, also müssen SIe ja im Server "zurückgehalten" werden. Hatte schonmal jemand so ein Problem?

Win 2003 Server mit Allen Updates
Exchange auch alle Updates