ImapSearchParameter.New might not be what you need - it searches for messages with the "Recent" flag - these are messages that recently arrived and your IMAP session is the first and only session notified about this. Try searching for messages without the "Seen" flag using this search parameter:
ImapSearchParameter.HasFlagsNoneOf(ImapMessageFlags.Seen)
In combination with a header search, that would be something like this:
Dim result As New ImapMessageCollection
result = client.Search( _
ImapSearchParameter.HasFlagsNoneOf(ImapMessageFlags.Seen), _
ImapSearchParameter.Header(headerName, queryTerm))