Exchange 5.5 sp3

We have recently been experiencing an issue when trying to delete a number of messages, move them to another folder or archiving them. We’ll get an error that says “Some items could not be deleted. They were either moved or already deleted, or access was denied.” Retrying the operation will then result in a few more of the messages getting either moved or deleted then the same error will appear. This will continue until all messages are deleted or moved often going about 10 messages at a time. We have no system errors, I’m thinking of running isinteg or eseutil, but wanted to see if anybody has had a similar issue. I haven’t tried upgrading to sp4. Thanks