Yep, you're right, the EntryID changes.
I've used Message ID, but you can only see/get it in the message header.
Public OlSentFolder As Outlook.Folder
Dim olPA As Outlook.PropertyAccessor
Dim messageID as String
Dim myOutlook As Outlook.Application
Dim olNamespace As Outlook.NameSpace
Set myOutlook = GetObject(, "Outlook.Application")
Set olNamespace = myOutlook.GetNamespace("MAPI")
Set OlSentFolder = olNamespace.GetDefaultFolder(olFolderSentMail)
Set olPA = olSentFolder.Items(i).PropertyAccessor
messageID = olPA.GetProperty("http://schemas.microsoft.com/mapi/proptag/0x1035001E")
The Message ID will look something like this: <008401cef84c$5a2d3c40$0e87b4c0$@company.com>
Here is some example code to get a message by MessageID:
Function GetEmailItemByID(id As String) As Outlook.MailItem
Dim findItems As Outlook.Items
Dim query As String
query = "@SQL=""http://schemas.microsoft.com/mapi/proptag/0x1035001E"" = '" & id & "'"
Set findItems = OlSentFolder.Items.Restrict(query)
If findItems.Count <> 1 Then
Debug.Print "Something is wrong - MessageID not found or >1 found."
Else
Set GetEmailItemByID = findItems.Item(1)
End If
End Function