The reason according to the MS documentation is:
when you move or copy an email message into a different folder, a
new item is created in the new folder with a unique item ID, and the
original message is deleted.
Therefore you get the exception: The specified object was not found in the store.
How to work around it?
Before processing an email messasge, create a custom extended property and set it on the email message and save the email message, to share the new state with the EWS server.
Guid myPropertySetId = new Guid("{20B5C09F-7CAD-44c6-BDBF-8FCBEEA08544}");
ExtendedPropertyDefinition myExtendedPropertyDefinition = new ExtendedPropertyDefinition(myPropertySetId, "MyExtendedPropertyName", MapiPropertyType.String);
message.SetExtendedProperty(myExtendedPropertyDefinition, "MyExtendedPropertyValueIdentifingAnEmailMessageToBeMoved");
message.SendAndSaveCopy();
Store the value of the myExtendedPropertyDefinition
(in the above example: "MyExtendedPropertyValueIdentifingAnEmailMessageToBeMoved"
) before you move the email message. Then you can move the email message to its destination folder.
After the original email has been processed (moved > deleted), you can find the email message at its new destination by seaching for the custom property and the value you stored to identify the email message:
ItemView view = new ItemView(5);
SearchFilter searchFilter = new SearchFilter.IsEqualTo(myExtendedPropertyDefinition, "MyExtendedPropertyValueIdentifingAnEmailMessageToBeMoved");
view.PropertySet = new PropertySet(BasePropertySet.IdOnly, ItemSchema.Subject, myExtendedPropertyDefinition);
FindItemsResults<Item> findResults = service.FindItems(WellKnownFolderName.SentItems, searchFilter, view);
Use for every email message a unique identifying value in order to get one search result.
Please note that this work around is the officially (by MS) suggested approach as described in the documentation.