When trying to export a mailbox to a PST, I received the following error in ExMerge :
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)
I verified the account I was using to export the mailbox had full control over the database per http://www.microsoft.com/technet/prodtechnol/exchange/guides/UseE2k3RecStorGrps/1ed0d5af-7dff-4cc3-9a05-f46d292ac5f4.mspx. This did not seem to help.
What I finally ended up doing to resolve the problem was detaching the mailbox from the user account and reattaching it. (Remove Exchange Attributes) For some reason this seemed to work.
Update:
I have also discovered this will happen when trying to export the mailbox on an account that is disabled. If your security policy allows, enable the account to export mailbox.