What happens if you run an IEMSTest.exe for a user ...
Here's some sample output:
C:\Program Files\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 - Exchange Admin.
Opening message store for Test User using /o=MSG1 ORG/ou=First Administrative Group/cn=Recipients/cn=testuser1826 /o=MSG1 ORG/ou=First Administrative Group/cn=Configuration/cn=Servers/cn=SERVER01/cn=Microsoft Private MDB.
Test User's Mailbox opened successfully.
Root Folder opened successfully.
Folder created successfully.
Test folder deleted successfully.
Test completed successfully for Test User.
BES Should be installed as the BES Admin account you use.