I just had to rebuild our Exchange 2003 (on Win2k3r2) server recently, and now a couple existing users are having issues. I created a new temporary user, and it is affected as well.
When operating in cached mode both receive the error: "Cannot open your default email folders. You do not have sufficient permission to perform this operation on this object. See the folder contact or your system administrator."
In non-cached mode, all folders public & private are accessible, and there are no errors when sending/receiving mail or calendar items.
I've tried solutions listed in
https://www.experts-exchange.com/questions/22679190/Outlook-2007-permissions-problems.html
and
http://www.activedir.org/Articles/tabid/54/articleType/ArticleView/articleId/25/Outlook-2007-Permissions-Issue.aspx
but the problem persists.
I've also compared the SELF permissions on the advanced mailbox properties, and everything matches up.
All other users are using Outlook 2007 in cached mode.
Are these PCs laptops that are removed from the Office?
Otherwise, if these are stationary PCs or Laptops, leave Cached Exchange Mode Off as it can causes various issues.