I have been working on a Hybrid Exchange project recently and when I was using my own laptop on my customer's domain , I could connect to a test exchange online mailbox without any issues.
But any machine on their network could not connect via autodiscover to an exchange online mailbox.So a couple of points to note.
When running an exchange hybrid the 'autodiscover.contoso.com' will point at your hybrid servers and when the outlook client hits the hybrid server the client will be directed to the correct mailbox location by the hybrid server.
So our good friend the Exchange Remote Connectivity Analyzer can perform a test on both an on prem exchange mailbox and an office365 mailbox and when the outlook client hits the https://autodiscover.contoso.com/autodiscover/autodiscover.xml the outlook client gets routed to the correct mailbox. But in the case of an exchange online mailbox , http redirection occurs until it reaches the exchange online autodiscover.xml which for example could be https://autodisocver.contoso.mail.onmicrosoft.com/autodiscover/autodiscover.xml
Another test we can do is by running the 'Test Email AutoConfiguration' tool in Outlook as per the image below. There are quite a few re-directs until outlook finds the correct exchange online mailbox.
So in my particular scenario my Outlook could connect fine but domain joined laptops could not and this was because of a group policy which is displayed below which was blocking the http redirects required to connect to the exchange online mailbox.
So how to fix this , well firstly remove the group policy and secondly you can edit 4 registry settings as follows and as per the image below in hkey_current_user\software\microsoft\office\14.0\outlook\autodiscover
So now all your Outlook clients in Hybrid mode will be able to connect via autodiscover.