Unable to migrate mailboxes

You need to create new mailboxes for the users. Once you have new mailboxes for them, the Restore-Mailbox command will use that mailbox instead of trying (and failing) to find the old mailbox.

Option 1 Spend some money:

I would try Aid4Mail to convert massive amounts of .mboxes to .pst's for importing in to Exchange. I have used this recently with great success.

At a $40 price tag it is relatively cheap. I hate spending money on software when I don't have to, but sometimes you have to bite the bullet if you want something down in a time effective manner, which it sounds like you do.

Option 2 spend a lot of time:

If you do not feel like spending $40 you can convert the .mbox files in to .eml files with a Free MBOX to EML utility. You can then import these .eml files in to Outlook. Then from Outlook you can export the mailbox in to a .pst that can then be imported in to Exchange. As you can probably already tell this is going to take a long time.

Edit:

As you are a moving to a new exchange environment I would look in to enforcing mailbox size limits and auto archiving. 10 GB mailboxes is abnormally large size from my experience.