We had the same problem which was caused by McAffe anti spam. We thought that the spam was being deleted but it wasn't. We had to manually delete the 'deleted' spam. Then it worked fine.
The problem soon came back though and now we run it without the anti spam software and without problems.