This was is a good one and has been doing my head in!
I had a user mailbox that could log in to OWA but not Outlook.
With outlook you would get an error saying:
"Cannot open your default e-mail folders. Microsoft Exchange is not available. Ether there are network problems or the exchange Computer is down for maintenance"
If you run:
Get-LogonStatistics -Identity <email address>
Then have a look at the FullMailboxDirectoryName
This should match the users legacyexchangedn. In my case, another user has the same address as a proxy address.
Just removed it and everything worked fine!