Yes, this is possible and looks like a good idea:
' select the target folder
imap.SelectFolder("Target Folder")
' search for messages with the specified messageId in "Message-Id" header
Dim list as ImapMessageCollection = imap.Search(ImapListFields.UniqueId, ImapSearchParameter.Header("Message-Id", messageId))
' of the number of messages found is not 1, report error
If list.Count <> 1 Then
Throw New ApplicationException("None or multiple message found.")
End If
' get the new message ID
Dim newUniqueId As String = list(0).UniqueId
Please note that not all messages are guaranteed to have message ID, and not all message IDs are guaranteed to be unique (because they are generated by the sender). However, the code above should work in almost all cases.