How to recover data from an Exchange 2013 database after a complete Active Directory loss?

Turned out this is a lot easier than I expected.

Any Exchange 2013 database can be mounted on any Exchange 2013 server, regardless of the organization and/or Active Directory domain (although the same or higher CU level is probably required for the server).

If a foreign database is mounted on a server, it will work perfectly and can even be used to store new mailboxes; all mailboxes in the DB will be treated as disconnected ones, and they can be connected to user accounts, can be used without any issue and can (of course) be exported.
Database portability, indeed! Looks like we are there yet, after all.

So, the process to recover data from an Exchange database when the original environment is unavailable goes as follows:

• Build a new Active Directory domain and a new Exchange 2013 server (or even use an existing one, if you have it available); they can be named as you wish, all names are completely irrelevant.
• Create a new empty mailbox database; the DB name and the file paths don't matter at all.
• Allow the database to be overwritten from a restore.
• Get the EDB file from the original server and ensure it's in a clean shutdown state (if it's not, use eseutil and the original transaction logs to perform a standard database recovery).
• Place the EDB file where the new Exchange server expects to find the new database (you can rename it if needed).
• Mount the database.
• Get a list of the mailboxes in the database using the Get-MailboxStatistics cmdlet.
• Create as many user accounts as required to reconnect the mailboxes you want to recover.
• Connect the mailboxes in the database to the new user accounts using the Connect-Mailbox cmdlet.

That's it; now you can use the recovered maiboxes, or you can export them to PST files using the New-MailboxExportRequest cmdlet.

If all you want to do is recover items, then yes, it is as simple as you say, but your steps are a bit off.

1. Install new Exchange server.
2. Create new mailbox databases. (Make sure they are circularly logged to speed up the restore time.)
3. Mount old databases as recovery databases.
4. Restart-Service MSExchangeIS
5. For each mailbox: run the New-MailboxRestoreRequest command.

In case it wasn't obvious, you'll need enough free space to have a second copy of the mailbox databases.

Note that any special folder permissions, delegations, Full Access and Send As rights will be broken or missing.

However, the bright side of all this is that NOTHING needs to match. You simply provide source and target mailboxes to the New-MailboxRestoreRequest and it copies the items.

You will probably have to figure out the old x.500 addresses and add them to the new mailboxes. Otherwise, replying to old messages won't work.