I have recently spent a considerable amount of time supporting one of our customers who for some reason was unable to perform MAPILOGONEx command via MFCMAPI. We were issuing the OPENSTORE_USE_ADMIN_PRIVILEGE OPENSTORE_TAKE_OWNERSHIP which translate to using Administrative Previleges.
After much speculation about lack of permissions, it turned out that customer's environment was at Exchange 2003 SP2 but did not have a fix for msExchMasterAccountSid issue. That same issue that even had msexchange.org guys write a tool, NoMas. Apparently, Information Store disallows the administrative permission resolution as well. NoMas can help a lot with the short-term workaround, while applying KB916783 ensures the correct behavior.
Now, I need to actually look at some of our apps and review their functionality under this scenario.