Please add the following registry key to your Exchange Server:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\MSExchangeIS\VirusScan
ProactiveScanning REG_DWORD 1
You will haveto reboot the server afterwards to make the setting stick.
If that does not sort it out, please let me know what Anti-Virus software you are using on the server.