I have written a sample which can be used by developers and Exchange Admins for handling issues with their custom code doing Autodiscovery.  I have and several others have used this sample as a base-line for testing and for code harvesting for a while.  I wanted to share this with you so that you might benefit.

This sample uses the Exchange Managed API 1.1 to call the AutoDiscovery, which is part of Exchange Web Services (EWS). It handles callbacks for doing redirection and certificates.  Logging is provided for referrels, redirection, certificates and network activity. This code will work for both on-premise and hosted Exchange servers such as Exchange Online/Office 365.

Autodiscover Checker
http://code.msdn.microsoft.com/Autodiscover-Checker-e1ebca42

This unsupported sample provides help by demonstrating how to properly call the Exchange AutoDiscovery web service. Executing the built application can be used
for gathering information on what is accessed during the AutoDiscover process and also be used for troubleshooting. If you use the code or executable, you
are responsible for its usage and will need to take ownership of the code - you should also only use this in a test lab and not production.

This is sample code and there are no implied warranties or guarantees as to its behavior. If you use this app or its code, you need to take 100% responsibility
for its code and its usage. It’s considered to be unsupported sample code which demonstrates the concept of doing AutoDiscovery with the Exchange Managed API and
should only be used in a lab environment.

If your having issue with the Exchagne Managed API going against Exchange Online/Office 365 and doing AutoDiscovery, the you should review the code. Code using the Exchange Managed API needs to have setup a callback for handling redirection.  This is accomplished by setting the RedirectionUrlValidationCallback property on the service object.  Without this being implemented, your code will not work.   Please review the article below for more information:

Working with Authentication in Microsoft Exchange Online
http://msdn.microsoft.com/en-us/library/gg194011(EXCHG.140).aspx

For external autodiscovery and connectivity checker, be sure to look at the Remote Connectivity Analyzer.

Remote Connectivity Analyzer
https://www.testexchangeconnectivity.com