So after looking around for a day or two, I'll throw this gem of an issue out there and see if anyone has seen this:
We have end users connecting to PF using Outlook 2010 (and some using 2003, pretty sure they see the same error) and when accessing folders that ALL USERS have REVIEWER access, they are told they don't have appropriate permissions to open / read emails stored in folders (which all parent objects again show EVERYONE to have REVIEWER priviledges). When using Webmail, however, it seems to function properly.
Users are mostly in WinXP environments and using Exchange with cached mode turned off. VPN and local users, configured the same except for the VPN connection, experience the same issue. 2003 and 2010 users experience the same issues, too.
This is the closest description I've been able to find concerning this issue, which makes the situation look dire:
Experts Challenge: MAPI is unable to access Public Folder store items
Any help is greatly appreciated!