Whether or not EntryID changes when an item is moved to another folder or
deleted to Deleted Items depends on the MAPI store provider. As it happens,
in a PST store (standalone) the EntryID does not change when an item is
moved within that store. It does change in the case of an Exchange mailbox.
At the MAPI level (or using a lower level API such as Redemption), you can
grab the PR_SEARCH_KEY (0x300B0102 or
") property to get a
more permanent ID in the case of an Exchange mailbox.
If you are using Outlook 2007 you can use PropertyAccessor to grab that
property using the DASL string property tag I provided.