I have found that if I move a message using IMAPIFolder::CopyMessages (using the MESSAGE_MOVE flag) the message gets a new entry ID. However I do not see any reliable way of getting the entry ID of the message in its new location, or otherwise getting a reference to it. The best suggestion I have had so far involves tagging the message with the old custom property before moving, and then doing a search afterwards, but I was wondering if there is a less convoluted solution.