I solved this one but wanted to share it for any exchange guys. Absurd problem that drove me insane for a week.
Get a ticket that outlook and activesync auto discover don't work. Well, work for everyone except a handful of users. All users, for various reasons, are having outlook accounts configured from start. Ok. We have a commonality.
Bad news: hosted Exchange; managed service. Call the provider. "Autodiscover issue; check CAS, internal/external URLs, etc." As usual: "Nothing wrong."
Go to a client. Trying auto configure in outlook for any affected users returns one of 3 errors about not being able to connect to account. Manual config works, and autodiscover redirection pop up appears, but no auto discover features work (free/busy info, automatic replies, outlook anywhere). Outlook 2013 or 2010, Windows 7 or 10, corporate image or factory image, internal or external network makes no difference. Same result. Free/busy kind of important for scheduling meetings, so this is starting to become a fucking problem. Wouldn't you know it most of affected users are upper-levels managers who schedule a lot of meetings. OWA still works normally, so at least a workaround.
Start going down the list. DNS, registry, local XML, firewall/webfilter. Service provider continues to claim must be local. Outlook auto configure test fails at http redirect with error 400. Similarly, going to autodiscover URL and using any of affected user credentials returns "Error 400 - request headers too long." Manual http redirect settings in outlook do nothing. At this point I discover I'm affected by the issue! Great. At least I can use myself as the test. Also notice using random other users' credentials tests successfully.
Ok, so related to account but the shit does not make sense. Read through millions of Microsoft articles and technet threads. Similar issues, some related to 2007 and 2013 coexistence but pretty sure service provider is not doing that and none of the other solutions work. Finally stumble on an OLD ass article about "request headers too long" error related to IIS requests. This is where it gets interesting. When a user is part of many AD groups, kerberos token increases in size. The http request to IIS includes the token in a header. More groups = larger header. If header is too big, error 400.
Let's test it on myself. So, remove myself from a bunch of groups (belonged to 90). Wait 15 mins. Run outlook auto configure test, testconnectivity.microsoft.com and URL test. Guess what? Successful! Restart Outlook and all autodiscover services now work. Clean up membership for affected users and we're back in business.
Apparently though this issue is fixed in Server 2008 R2 and above. I fail to believe service provider is not on R2 but maybe they are? We'll see. Just glad this is over.