1) Only affecting users who have Outlook Anywhere group policies pushed down to their machine
2) Only happening when in the office and on the LAN (fine when out of the office using Outlook Anywhere)
3) Happening on Outlook 2010 and 2013 (Exchange 2010 Server)
I initially thought it was an Outlook Anywhere issue. Using trial and error, I started disabling some of the settings we push down using group policy but it did not seem to have an effect.
I finally discovered the issue wasn't directly with Outlook Anywhere, but in fact Autodiscover! Again, using trial and error, the particular issue was caused by Outlook trying to query the autodisover service based on the primary SMTP address, for example firstname.lastname@example.org it would be trying to connect to https://abc.com/autodiscover/autodiscover.xml - in my case this connects nowhere (should this work and therefore do I have something set up incorrectly?)
To disable this, in group policy go to User Configuration | Policies | Administrative Templates | Microsoft Outlook 2013* | Account Settings | Exchange | Disable AutoDiscover
Select "Exclude the root domain query based on your primary SMTP address"
* Note, that in order to configure Microsoft Office through Group Policy, you'll need to download the ADMX and ADML files and place them in the required locations (see http://windowsitpro.com/windows/q-how-do-i-import-admx-file-my-computer)