Issue: ~5 users were complaining that they were unable to Reply All, add a calendar entry and print while using Outlook. When the users clicked "Reply All" the following message appeared:

"The connection to Microsoft Exchange is unavailable. Outlook musst be online or connected to complete this"

 

Other symptoms included the users being prompted for the password. Exchange showed as being connected fine. OWA was working fine.  

After a lot of searching it appeared the Exchange Server has rebooted the evening before and the  "Microsoft Exchange Address Book" service had not started despite it being set to Automatic. I started this service manually and requested all the users to log in and out of Outlook. All sorted.