Hi Robin,
I would hate to bring up something simple, but try uninstalling your virus scanner (if you have one). Just disabling it probably won't do. If your scanner isn't fully Exchange aware (and don't trust anyone who just says that theirs is) then this is exactly the kind of issue you will experience.
As a second solution, I would suggest checking whether you have a good database to begin with. By that, I mean you will want to run both:
eseutil /g
isinteg -test alltests -fix
You will need to do some reason on these commands, and take your system offline first. Again, if you have any tiny corruption, it will cause exactly the issue you are seeing.