(I just copied my post from the Microsoft forums here). Original thread: http://community.office365.com/en-us/forums/160/p/62614/261211.aspx

This problem was due to the number of concurrent HTTPS connections used by Outlook-Anywhere, especially in the case of shared calendars, shared mailboxes, and delegated access. The problem is exacerbated by the fact that users are randomly placed at different server locations (various servers within Dublin and Amsterdam for EMEA users). I opened a case to try to get all the users put on the same mailbox sever/cluster, but that wasn’t possible. I began re-creating uses repeatedly in an attempt to get them all in the same location, but I realised I was probably not going to get things improved enough anyway.

The issue was that the broadband, provided by the serviced office building, could not handle those concurrent connections (8 or 9 concurrent HTTPS connections per Outlook client), or was attempting to load balance them or something. I tried and tried and tried to get the building’s IT contact, and their IT contractors, to look into restrictions in the number of concurrent connections, or load balancing/proxying, or whatever was wrong at their router/firewall, but I had no joy. They just kept offering more bandwidth, lower contention (1:1), and telling me that there were no restrictions.

Well, in the end, to solve the problem, I bought a hosted-VPN account (£3.99/month PPTP account, as used by people who want to hide/change their location on the web), and configured a Mikrotik router to route all Microsoft destinations through this PPTP service. The customer was delighted at the results. Up until this point, I don’t think they believed me that it actually “normally worked quite fast”.

I set the Mikrotik to establish a connection to the hosted PPTP VPN service, and route the following CIDR ranges through that tunnel:

I had to route just Microsoft stuff through the VPN, instead of the easier option of routing everything through the VPN (default route to VPN), because it became apparent that quite a few websites didn’t work via this particular VPN provider. I guess they might get blacklisted, or they are low-maintenance (you get what you pay for..). Anyway it was easier than trying other providers, or opening more support tickets, etc.

What this means is that there is only a single connection going out through the broadband for Office 365, for the entire company, thus overcoming the problem.

While it is clear that the broadband is at fault (it is a serviced office building – the customer cannot install their own broadband or telephone lines), I think Microsoft should look at either providing VPN access to the Exchange severs, in the same way most of the world used to access Exchange in the pre RPC/HTTP days, or they might look to optimize the number of connections that are used. 9 connections per client is quite high in my opinion.

p.s. Mikrotik = super.