Getting messages asynchronously using MailKit
It's hard to say how to write the ideal method for your use-case because you don't specify some of the details that would be necessary to know, such as:

How often will your code be making this query?

Is the connection always to the same IMAP server, username and password?

(if it'll be called fairly frequently with the same server/username/password combo, you could try to re-use the same ImapClient connection)

That said, I'll start with trying to at least clean up the code a bit.

public async Task&lt;IList&lt;IEmail&gt;&gt; EmailQueryAsync(string query, Action&lt;IEmail&gt; callBack)
{
    return Task.Factory.StartNew (() =&gt; {
        var result = new List&lt;IEmail&gt;();

        using (var client = new ImapClient ()) {
            client.Connect ("imap.gmail.com", 993, true);

            client.AuthenticationMechanisms.Remove ("XOAUTH2");

            client.Authenticate (this.userName, this.password);

            var folder = client.Inbox;

            folder.Open (FolderAccess.ReadOnly);

            var uids = client.Inbox.Search (SearchQuery.FromContains (query));

            foreach (var uid in uids) {
                var message = folder.GetMessage (uid);

                var email = new Email (date: message.Date, id: message.MessageId, messageBody: message.TextBody, references: message.References);

                callBack (email);

                result.Add (email);
            }

            return result;
        }
    }
}


I changed your code to put the entire block of logic into a single task which will all run on the same thread rather than your previous block which would effectively just run synchronously anyway since it didn't actually parallelize anything (it can't, really, since you can't search a folder until you've opened the folder - which you can't do until you've authenticated - which you can't do until you've connected, etc).

As far replacing your GetMessageAsync() logic goes, since the ImapClient can only process a single command at a time anyway, it doesn't make sense to spawn potentially thousands of command tasks asynchronously so that they can all just hurry up and wait for the previously queued tasks. Better to just write a synchronous loop in this scenario.

Update 2017-12-14: This will no longer be the case in MailKit 2.0. 2.0 will no longer wrap the synchronous calls using Task.Run() which means that they will no longer spawn threads.