Seeing from the logs how big your mailbox is (634'037 emails), my assumption is the server is not able to search through the mailbox without timing out.
You can limit your serach -or- extend the timeout.
All queries are executed by the IMAP server.
Mail.dll simply issues a query and receives results. In this case it is a very simple query, and server shouldn't have any problems executing it.
However it looks like server is note returning anything within default timeout. Please note that this indicates a server side issue.
Here are a couple of things you may try:
If your mailbox is really big try increasing read timeout:
imap.ReceiveTimeout = TimeSpan.FromSeconds(60);
Does using a Expression.Subject work:
Does using a string that for sure doesn't exist in the mailbox work:
Does using a
Are you using some non-letter characters in your search (e.g. quotes, apostrophes)?
Mail.dll should encode those properly, but maybe the server is not following the spec correctly.
Please turn on logging: