Outlook 2016 connectivity to Office 365. DNS or autodiscover problem?

I have the problem that I cannot connect and Outlook 2016 to Office 365, autodiscover doesn't seem to be functional. I have tried on tow computers and no such luck. I can log in on https://portal.office.com with the credentials so that is not the problem. I guess the problem is in the DNS the domain is frimannveje.dk if anyone wants to look into it.
Per JacobsenSystem TechnicianAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Vasil Michev (MVP)Commented:
Your autodiscover record seems OK. Just to be on the safe side, perform the Autodiscover test from ExRCA here: https://testconnectivity.microsoft.com/
You can also do a similar test via Outlook: hold the CTRL key, right-click on Outlook's icon in the tray, Test E-Mail Autoconfiguration, enter unsername and password, clear the two Guessmart checkboxes and run the test.

Have you tried via computer outside of the domain network, just to exclude local DNS/network issues? Also, does OWA work (https://outlook.office.com/)? What license do you have assigned to the user?
Could you please attach the screenshot of the outlook error while configuring outlook?
Per JacobsenSystem TechnicianAuthor Commented:
https://testconnectivity.microsoft.com/ tests ok, with an exclamationmark though, but that should be ok.

OWA works

I tried other DNS servers, and a mobile internet connection that also didn't help.

I all the time end up with this one "There is no encryped connection..."
Determine the Perfect Price for Your IT Services

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden with our free interactive tool and use it to determine the right price for your IT services. Download your free eBook now!

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Todd NelsonSystems EngineerCommented:
Is this with one (or a few) mailboxes or all mailboxes?

Was this mailbox moved from an on premises Exchange organization to EXO?
Per JacobsenSystem TechnicianAuthor Commented:
All mailboxes seem to be affected. No, theese mailboxes, and the domain are brand new.
Vasil Michev (MVP)Commented:
Did you try on an external PC? Your CNAME record resolves correctly externally, but you might as well have internal DNS and/or SCP pointing to the wrong location, so make sure you check/fix that. A quick way to test without making any server changes is to use the reg keys detailed in this article to "instruct" Outlook to bypass the local autodiscover process: http://support.microsoft.com/kb/2212902

The only thing you need working for O365 is the CNAME (HTTP redirect) method, you can block all else via the reg keys and see if Outlook works.
Per JacobsenSystem TechnicianAuthor Commented:
This is what did it, adding the account from inside Outlook 2016, as he writes totally different UI and it works.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Microsoft Office

From novice to tech pro — start learning today.