Hi,
From your description, Outlook clients can connect to Exchange server but the connection is slow. Please make sure all Exchange services (Autodiscover, Availability service/free busy information, OOF, OAB etc.) work well in Outlook.
If all services can be used from Outlook and the issue persists, I recommend you follow the steps below for troubleshooting:
1. Disable IPv6 via the registry for Exchange 2013.
http://support.microsoft.com/kb/929852
2. If there is a proxy server configured in IE, please uncheck it. Unselect bypass proxy server for local addresses in IE manual proxy configuration screen. Let IE automatically detect proxy settings instead of manual settings.
Hope this can be helpful to you.
Best regards,
If you have feedback for TechNet Subscriber Support, contact
tnmff@microsoft.c