ExMerge Failing

Error opening message store (MSEMS). Verify that the Microsoft Exchange Information Store service is running and that you have the correct permissions to log on. (0x8004011d)

*** are you running Exmerge as the administrator?

http://support.microsoft.com/kb/273642/
ExMerge Does Not Work Unless You Have Receive As and Send As Permissions on the Store

By default the admin accounts are specifically denied the SendAs & ReceiveAs rights, so you need to remove those deny permissions, or create a non-admin account for doing Exmerge.

To resolve this issue, grant the account that you are using to run ExMerge Receive As and Send As permissions on the Mailbox store:

1. Start Exchange System Manager, and under Administrative Groups, locate the Mailbox store.
2. Right-click the Mailbox store, click Properties, and then click the Security tab.
3. On the Security tab, in the top pane click the account that you are logged on as, and in the bottom pane, click to select the Receive As and Send As check boxes to grant these permissions to that account.
4. Click OK. This account now has full permissions to log on to the mailbox store, and to export or import messages for every mailbox.
5. Grant Send As and Receive As permissions to this administrator account on all the mailbox stores against which you need to run ExMerge.

Note When you are ready to process the data from the new stores, stop the SMTP service. By stopping the SMTP service, no new e-mail messages are delivered to the new stores while you are running ExMerge.

After you grant these permissions, ExMerge runs successfully.