We were having performance issues after we first went from onsite exchange to 365, most people couldn't even load outlook without an error as it was so slow. We now have cached mode turned off and everything works about as well as onsite did! We found in DNS our proxy had 3 entries (One for it's domain IP, one for the wireless IP and one for it's heartbeat to the failover) we removed the wireless and heartbeat entries as they aren't needed by any domain computers and ran a ipconfig /flushdns on all computers Outlook started to run exactly as expected! Double check your DNS for entries to check there are no duplicate entries for your proxy as it seems to pick one at random and then time out.