This applies only to Windows Vista, 7, 2008, 2008R2, 2012, 8.
As far as I know, this applies to all office versions.
The set of folders cannot be opened.The information store could not be opened.
If you receive the above error, and you are sure that the server and exchange mailbox store are working correctly (Webmail works, other users can connect), and you have tried to create a new profile only to get the same error. Check to see if on the outlook shortcut, compatibility mode is set. If so, remove it! Outlook can’t connect to exchange when run in compatibility mode.
In my specific case, the store had been offline before this error and the user kept trying to start outlook. I suspect that at a given moment windows suggest to try compatibility mode. After everyone else was back online this user could not, because of this compatibility mode setting. Check on all the shortcuts, check the all users settings, check the outlook.exe in explorer.