Exmerge – Permissions Error

When running the Microsoft Exmerge utility, you may receive the following error in your exmerge.log file:
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. (0×8004011d)
Even though you may be a Domain Admin or Enterprise Admin, you will still receive [...]