A family of Microsoft relational database management systems designed for ease of use.
Just an update on this, we had the same issue here and none of the previous suggestions worked.
Our fix was to remove multiple mailboxes from the same .OST file. Our users had a primary mailbox set up in Outlook, and another shared mailbox stored in the same file. Removing the shared mailbox and putting it in its own .OST file appeared to work and we can now connect to that mailbox from Access.
Note that in our situation it was only this particular mailbox which wasn't working with Access (the rest were fine). This was on a Windows Server 2008 R2 installation, Remote Desktop Services account. Outlook and Access 2010. It was not a system wide setting which caused the problem, because the other accounts on the system kept having the error message until we followed these steps.
Hope this helps someone!