Sorry, I missed you need to apply some search criteria. In this case a little bit optimal code can be used. It is optimal in case the search returns a lot of emails, but you want only recent 10.
// maximal number of recent messages
private const int MaxRecentCount = 10;
private List<ImapMessageInfo> MultiSearch(Imap imap, ImapListFields fields, ImapSearchParameter criteria, params string[] folders)
{
    // search within each folder, but retrieve only UniqueId and ReceivedDate
    List<FolderMessageInfoPair> list = new List<FolderMessageInfoPair>();
    foreach (string folder in folders)
    {
        imap.SelectFolder(folder);
        ImapMessageCollection col = imap.Search(ImapListFields.UniqueId | ImapListFields.ReceivedDate, criteria);
        foreach (ImapMessageInfo info in col)
        {
            list.Add(new FolderMessageInfoPair(folder, info));
        }
    }
    list.Sort();
    // remove unwanted messages
    if (list.Count > MaxRecentCount)
        list.RemoveRange(0, list.Count - MaxRecentCount);
    // get full info of messages we found, each from its folder
    List<ImapMessageInfo> ret = new List<ImapMessageInfo>();
    foreach (string folder in folders)
    {
        bool search = false;
        ImapMessageSet set = new ImapMessageSet();
        foreach (FolderMessageInfoPair pair in list)
        {
            if (pair.Folder == folder)
            {
                search = true;
                set.Add(pair.MessageInfo.UniqueId);
            }
        }
        if (search)
        {
            imap.SelectFolder(folder);
            ImapMessageCollection col = imap.GetMessageList(set, fields);
            ret.AddRange(col);
        }
    }
    return ret;
}
// helper class for MultiSearch method
private class FolderMessageInfoPair : IComparable<FolderMessageInfoPair>
{
    public string Folder { get; private set; }
    public ImapMessageInfo MessageInfo { get; private set; }
    public FolderMessageInfoPair(string folder, ImapMessageInfo messageInfo)
    {
        Folder = folder;
        MessageInfo = messageInfo;
    }
    // compares two instances according to ReceivedDate
    int IComparable<FolderMessageInfoPair>.CompareTo(FolderMessageInfoPair other)
    {
        return MessageInfo.ReceivedDate.UniversalTime.CompareTo(other.MessageInfo.ReceivedDate.UniversalTime);
    }
}
The method can be used as follows:
List<ImapMessageInfo> col = MultiSearch(imap, ImapListFields.Envelope, ImapSearchParameter.All, "Inbox", "folder2", "folder3");