I am trying to restore a mailbox from recovery storage group. But I am getting a message "No mailboxes match the matching criteria" in the Select mailboxes to copy or Merge window. Please note that I have created two new mailboxes which were deleted from exchange and AD earlier and then we are trying to get the mails from the backup for these mailboxes.

Hi, Please restore AD account first and then try to recover the mailbox. How to restore deleted user accounts and their group memberships in Active Directory http://support.microsoft.com/kb/840001Xiu Zhang TechNet Community Support