According to our documentation, DeleteItem calls should fail with a ErrorStaleObject error when the ChangeKey is not the most recent one. This, however, is not the case. In Exchange 2007, the ChangeKey is completely ignored in DeleteItem calls. This decision was made on the logic that if you are trying to delete an item, chances are you don’t care if you have the most recent copy or not. But, what if you do?
You could try doing a GetItem, check the ChangeKey and then call DeleteItem right after, but that still leaves a small window of time between your GetItem and your DeleteItem calls where the item may have been changed.
Here’s a workaround which will help you implement the logic yourself using pull notifications.