Office 2016 Will Not Connect to Office 365

I have recently performed three Exchange to Office 365 Migrations. In each I have had problems with Office 2016 not connecting to Autodiscover and thus Outlook won’t create the profile. In most cases I’ve used the Microsoft Support and Recovery Assistant to work around this. However, I need to determine what is causing this problem. It’s causing a lot of confusion, frustration, and probably hair loss. I’ve sunk a good 8 hours of troubleshooting, and so far I’ve had no luck. I’m hoping someone can help. Here’s what I’ve done:

• I’ve tested that Autodiscover itself is healthy using TestConnectivity.microsoft.com and by adding profiles on my phone off the network.
• I have tried to create a profile off the client’s network on my own machine.
• I’ve tried creating a profile on the network on my own machine, and off the network on the client’s machine.
• You get the picture, basically trying to rule out that a Domain level autodiscover issue is the problem, because that’s bit me in the but.
• I’ve tried uninstalling Office using the uninstall tool provided my Microsoft and reinstalling Office.
• I’ve tried created a new local Windows profile and creating the Outlook profile there.
• I’ve tried using registry edits to ignore any and all of the various stages of Autodiscover.
• I’ve created a non-AD synced user and tried with that profile to test it’s not a problem with the AD attributes coming over the sync.

I’m at a loss at what is causing Outlook to not connect to Office 365. I have three more migrations over the next couple months, so any suggestions y’all have would be appreciated.