"The connection to the Microsoft Exchange Server is unavailable. Outlook must be online or connected to complete this action."

See kb : http://support.microsoft.com/kb/2299468/en-us

What i do :

New-ThrottlingPolicy –name Outlook2003Calendar

Set-ThrottlingPolicy –identity Outlook2003Calendar –RCAMaxConcurrency 100

Set-Mailbox –Identity “annoyed user” –ThrottlingPolicy Outlook2003Calendar

You can make a script to execute the third line for all your users.