We hit a very annoying issue last week when one of our Office 365 using clients' autodiscover stopped working properly. Rather than using the autodiscover.domain.com for its settings, the autodiscover was failing when attempting to use an autodiscover service at domain.com. Our client's website happens to sit on our Linux web server fronted by CPanel. An update to CPanel last week (about 10th Feb 2015) caused the problem when they changed some autodiscover settings.
Autodiscover failing not only meant headaches in trying to connect Outlook to mailboxes, but users also found that any shared mailboxes that they were previously connected to also disappeared from their Outlook profiles. Having used www.testexchangeconnectivity.com's Office 365 Outlook Connectivity tests we could see that the autodiscover service was passing the first test when looking for autodiscover service on the root domain (e.g. domain.com), when really it should have failed this test (because the Exchange server, being on Office 365, is not on-premises) and then gone on to pass the test when looking for a service at autodiscover.domain.com. One option would have been to remove the A record for the root domain (domain.com) which pointed at our web server and simply rely on a www. subdomain. However, not everyone bothers to type www. in the address bar nowadays and so we saw it as being important to keep the ability to get to the website without typing www. at the start of the address.
We disabled the autodiscover service on the Linux webserver expecting this to fix the problem - but no joy. After much head scratching we found the following article which saved the day. Many thanks to JeffBeall as his suggested workaround did the trick. Autodiscover now works and the website can be accessed via domain.com (without the www.) http://community.office365.com/en-us/f/156/t/293985.aspx The risk with this fix is that when CPanel is next updated it could wipe the changes you have implemented. However, hopefully this 'bug' will have caused enough inconvenience to enough people to ensure that the next update works around the conflict that was caused by the most recent update.
EDIT - on 20th Feb 2015 it appears that there has been another CPanel update which looks like it has attempted to resolve the issue whereby 'Autodiscover must generate a 400 status when disabled'