I have this problem too, and when I examine the event log on the server, it has an entry witch refers to some invalid message in the BAD folder.
Sometimes it helps to shutdown all exchange services, delete the bad message (file name is in the event log), run a defrag, and restart the services...