Multiple autodiscover Cname entries needed

Skype clients do not use your mail autodiscover record. They need a Lyncdiscover record, for O365, normally pointing to webdir.online.lync.com and a SIP record pointing to sipdir.online.lync.com

Well they do rely on EWS for some features, and thus query the Autodiscover record. If it's only SfB clients you have problems with, this is most likely related to the use of Modern authentication/MFA, do you have it enabled for your users? And where is your SfB homed, on-premises or Online? Also, how do users authenticate against O365, do you use federation or?

Generally speaking, in Hybrid config the autodiscover record should indeed point to the on-premises server, so you can ignore the recommendations from the portal/wizard.

I have that but still cannot connect...see attached. The analyser shows i need it.

Vasil Michev (MVP), I don't quite understand all your questions.  I am a small business user who is just starting our with office 365.

 If it's only SfB clients you have problems with, this is most likely related to the use of Modern authentication/MFA, do you have it enabled for your users? I don't even know where to look for this setting.

And where is your SfB homed, on-premises or Online? I'm not sure what an SfB is. Explain and I can tell you.

Also, how do users authenticate against O365, do you use federation or? I'm not sure. I left it with the default, where do I check for that?

I apologize for not being more knowledgeable. I have an incident with Microsoft and they have been helping me but even THEY can't tell me how to get this to work

SfB stands for Skype for Business. In your original question, you said you were using Office 365 Skype for Business, correct? If so, did you enable Modern Authentication? By default it is off for Skype and Exchange online in older tenants (Pre 2017)  but on for newer ones. you can check using powershell. See this article. https://social.technet.microsoft.com/wiki/contents/articles/34339.skype-for-business-online-enable-your-tenant-for-modern-authentication.aspx
   If you check your Exchange Connectivity ( https://testconnectivity.microsoft.com/) does it pass the Autodiscover test?

And for Authentication, Do your users login on the Office 365 Portal or do they get redirected to an ADFS server? If you did not install an ADFS server in your environment, then you are not doing Federation.

Let me ask it like this, when you log in to O365 (or Outlook), do you get prompted to perform additional verification via your mobile phone (either via call, SMS or using the Authenticator app)?

Another thing you need to check for is the steps in this article: https://support.microsoft.com/en-us/help/2787614/conversation-history-contact-cards-free-busy-and-out-of-office-informa

Jeff, I enabled the auth as instructed in the article but only for skype not exchange. No better. Yest autodiscover passes using the analyser (but again, the autodiscover is pointing to my on-prem server, not autodiscover.outlook.com)

Vasil, No we do not get asked for any additional verification, just login name and password.

I did the lync analyzer from a computer outside my domain and all green but for some stupid reason I cannot run this within my domain, the verification fails almost instantly each time on multiple browsers.

Not sure if this helps but on the computer outside my domain, I connect to SfB and get the password prompt...and then it ask again for it 3 times then fails with same message as inside domain. I know the password is correct because one time I purposely entered the wrong password and it told me incorrect. So something is not happening when I enter the correct password.....Probably affecting both places but inside the domain it is using my current login credentials.