In my blog post on Workaround for Exchange 2010 & Outlook 2003 Shared Calendars Connectivity Issues "The connection to the Microsoft Exchange Server is unavailable. Outlook must be online or connected to complete this action."  I mention the excellent work of the Microsoft support Engineer on the case.  Well he’s published a very content rich blog about all this and other possible causes of the error notification on his TechNet blog: Things you need to know about “The connection to the Microsoft Exchange server in unavailable. Outlook must be online or connected to complete this action” prompts in an Outlook 2003–Exchange 2010 world. It’s a must read for all people dealing with this error message.