C:\Program Files (x86)\Research In Motion\BlackBerry Enterprise Server\Utility>IEMSTest.exe
BlackBerry Enterprise Server Utility - IEMSTest.exe (IExchangeManageStore), Version 1.0
Copyright (c) Research In Motion, Ltd. 1999. All rights reserved.
Opening Default Message Store Mailbox - BESAdmin
Eric Jones: Opening message store using
/o=First Organization/ou=first administrative group/cn=Recipients/cn=Eric
/o=First Organization/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)
/cn=Configuration/cn=Servers/cn=server2/cn=Microsoft Private MDB
Eric Jones: OpenMsgStore failed (8004011d)
Eric Jones: CDO Server Name: server2
Eric Jones: CDO Mailbox DN: /o=First Organization/ou=first administrative grou
Eric Jones: CDO logon successful
Eric Jones: Get default calendar folder successful
Eric Jones: Get calendar folder name successful: 'Calendar'
Eric Jones: CDO test completed successfully
Eric Jones: Active Directory permissions test completed successfully
As per the above output, the mailbox was not opened with error 8004011d. I ended up following these steps to adjust the throttling policy, which fixed the issue. After making the changes, I restarted the BB services and the Exchange services, and then the IEMStest passed and the mailboxes were accessible again.