Tip #1: Disable IPv6
IPv6 needs to be disabled on the server side if you are running Windows 2008.

1) Uncheck IPv6 in TCP/IP.
2) Start > Run type "drivers".  Go to etc folder.  Open hosts file in notepad.  Put # sign in from of this line to comment out — ::1 localhost.  So that line should look like this — #::1 localhost.
3) Open regedit. 
This method disables IPv6 on your LAN interfaces and connections, but does not disable IPv6 on tunnel interfaces or the IPv6 loopback interface.

Add the following registry value (DWORD type) set to 0xFFFFFFFF:

HKEY_LOCAL_MACHINESYSTEMCurrentControlSetServicesTcpip6ParametersDisabledComponents

This method disables IPv6 on all your LAN interfaces, connections, and tunnel interfaces but does not disable the IPv6 loopback interface. You must restart the computer for this registry value to take effect.

For additional information about the DisabledComponents registry value, see Configuring IPv6 with Windows Vista.

If you disable IPv6, you will not be able to use Windows Meeting Space or any application that relies on the Windows Peer-to-Peer Networking platform or the Teredo transition technology.

4) Reboot client machine and server after making these changes.

Tip #2: Double check your CertPrincipleName and Outlook Settings
In some cases, I have seen that the principle name should be your domain and not the full URL of your mail server.  To change, run this command from power shell:

set-OutlookProvider -id EXPR -CertPrincipalName "msstd:yourdomain.com"

Then, adjust your Outlook Anywhere settings in Outlook to match this.  Also, try clicking "On fast networks…" option.