There are tons of posts about this subject, but none of them offered the very simple solution that worked for me:
Make sure the Microsoft Exchange System Attendant is running on the mailbox server.
We had a catastrophic crash of a VM host, on which our Exchange 2013 server was running as a guest. Everything seemed to come back up just fine, and all Outlook users were back online with Exchange, except for two.
One user was running Outlook 2016 like the rest of the org, but one was running Outlook 2007 (don’t ask). They seemed to have nothing in common, but they both were throwing errors that network problems were preventing communication with the Exchange server.
I did all sorts of crap, resorting to deleting the Outlook profiles and re-creating them. But even when starting Outlook in safe mode without caching, it would complain about the network connectivity immediately.
Here’s the description of the Microsoft Exchange System Attendant:
Forwards directory lookups to a global catalog server for legacy Outlook clients, generates e-mail addresses and offline address books, updates free/busy information for legacy clients, and maintains permissions and group memberships for the server.
The emphasis is mine, because it’s a very strange situation. I understand why the Outlook 2007 client — which is very much legacy — wouldn’t work. But why this one particular Outlook 2016 client? Like I said, every other user in the organization uses 2016, and they were all working fine.
Anywho, I hope this helps someone out who might be seeing one of the same red herring errors:
Cannot start Microsoft Office Outlook. Unable to open the Outlook window. The set of folders could not be opened.
Unable to open your default e-mail folders. The Microsoft Exchange Server computer is not available. Either there are network problems or the Microsoft Exchange Server computer is down for maintenance.
The connection to the Microsoft Exchange Server is unavailable. Outlook must be online or connected to complete this action.
Unable to open your default e-mail folders. The information store could not be opened.
Outlook could not log on. Check to make sure you are connected to the network and are using the proper server and mailbox name. The connection to the Microsoft Exchange Server is unavailable. Outlook must be online or connected to complete this action.
