The problem was that a cpanel update created an autodiscover entry that superseded the standard autodiscover entry that Microsoft suggested customers put in place. This would affect domains in these situations:
1) Use Exchange as their email server (Office365 or any other Exchange server, on premise or outsourced)
2) Have a valid third party SSL certificate on their web site
3) Use WHM/cpanel on their web server
My clue that autodiscover was pointing to the wrong location (aside from the aforementioned problems) was that server replying with autodiscover.xml information was the domain's web server when running the Outlook Autodiscover test from https://testconnectivity.microsoft.com.
Implementations vary, but typically autodiscover (for Office365 at least) will be configured by a CNAME record of autodiscover.domain.com to autodiscover.outlook.com. In the case here, a WHM/cpanel update created a autodiscover response at https://domain.com/Autodiscover/Autodiscover.xml. Outlook checks https://domain.com/Autodiscover/Autodiscover.xml before it checks https://autodiscover.domain.com so if Outlook finds a response at https://domain.com/Autodiscover/Autodiscover.xml, you will have a problem.
In the case of the WHM/cpanel update, https://domain.com/Autodiscover/Autodiscover.xml would forward to https://cpanelemaildiscovery.cpanel.net/autodiscover/autodiscover.xml - which gave the incorrect autodiscover response.
There are two fixes.
The first/proper fix is to disable autodiscover using WHM. Log into your WHM in your web browser and log in as root. In my case, I logged in to my BlueHost WHM via http://220.127.116.11/whm (where 18.104.22.168 is your server's IP address). Go to Server Configuration -> Tweak Settings. Make sure Proxy subdomains is turned ON. Make sure Thunderbird and Outlook autodiscover and autoconfig support are turned OFF.
The second/manual fix (courtesy of comment at 2/14/2015 10:21 AM at http://community.office365.com/en-us/f/156/t/293985.aspx):
- Log in as root on your web server
- Edit /etc/httpd/conf/httpd.conf
- Search for autodiscover, you should find a ScriptAlias line referencing it
- Comment this line out or remove it completely
- Edit /usr/local/cpanel/APACHE_CONFIG and find the same line and remove it or comment it out
- on BlueHost, run "/usr/local/cpanel/bin/apache_conf_distiller --update"
- run "service httpd graceful" to restart apache
Afterwards, test your autodiscover via https://testconnectivity.microsoft.com and presuming a successful tests - all is well since the web server is no longer responding to autodiscover requests.