Auto discover is working for a user with an on premises mailbox.

The mailbox is moved to Office 365 using a Remote Remove Request. The user is no longer able to connect to their mailbox.

The Outlook Test E-mail AutoConfiguration tool may report the error 0x800C8205

The user's RemoteRoutingAddress address is incorrect, causing autodiscover to fail to redirect from the on premises Exchange server to Exchange Online.

[PS] C:\>Get-RemoteMailbox theether@domain.com | fl RemoteRoutingAddress

RemoteRoutingAddress : SMTP:theether@domain.com

Set this to the user's address:

[PS] C:\>Set-RemoteMailbox -Identity "domain.local/Users/The Ether" -RemoteRoutingAddress theether@domaincom.mail.onmicrosoft.com

Verify it is now correct:

[PS] C:\>Get-RemoteMailbox theether@domain.com | fl RemoteRoutingAddress

RemoteRoutingAddress : SMTP:theether@domaincom.mail.onmicrosoft.com

How to troubleshoot issues that prevent a user from viewing other users' free/busy information in Office Outlook 2007 and in Outlook 2010 in Office 365
http://support.microsoft.com/kb/2581088