Scenario One
Client was on Exchange 2007 and moving in this case to Office 365. The first problem that we encountered was with profile redirection. The user population was heavily populated with Citrix users with Outlook 2007. Of the population of users, 85% were on Citrix. With test accounts on Citrix we were never able to get an existing profile or a new Outlook profile to connect to the new server.
After a mailbox was moved, Outlook would popup with an error that an Action failed as well as a box that showed the user name and the old Exchange 2007 server. First it was noticed that they did not have a proper AutoDiscover record internally. With that record created, a new profile in Citrix would connect the new Exchange 2013. However an existing profile would not.
We examined Group Policies, login Scripts, etc. No configuration information was found. Then we did some digging into the profiles on the Citrix server and noticed a file called Custom12.prf. This file serves as the Configuration file for Office customizations.
[Note – for those not familiar with the OCT, check it out here]
When the PRF file was examined we found some preconfigured settings for Exchange.

Well, that would explain why our profiles were not connecting to the new server. Once we removed the PRF file from the mix, we were able to connect to Office 365. While the client had found it necessary to put these in place, we believe the initial settings were put in place because there was no AutoDiscover record for their domain inside or outside of their network. Using AutoDiscover (Exchange 2007+) would have alleviated this issue, negated the problems we found and the troubleshooting that we had to go through to find the issue.
So if you are having issues with AutoDiscover, make sure to check GPOs, OCT and more to make sure no customizations have been put in place that skips AutoDiscover.
Scenario Two
For this scenario, the client was upgrading from Exchange 2007 SP3 UR17 (the latest at the time of this article) to Exchange 2013 CU9. After the Exchange 2013 install we configured CAS coexistence with a new certificate, the Legacy namespace, the old namespace transferred to Exchange 2013, firewall rewritten to point traffic to 2013 and any other settings we needed to change. We then tested Outlook and OWA connections to both Exchange 2013 test mailboxes and 2007 production mailboxes.
This testing appeared to go well for our small test group of IT and external laptops (mine). Then we began a larger rollout and started to run into some sporadic issues with Outlook 2007 or 2013. Pop-ups were occurring with both internal AND external clients. The pop-ups are not for authentication. The errors are connection OR smartcard errors. What?!? Usually if AutoDiscover is broken the pop-up is an Authentication or a certificate error message (mismatched, wrong name, etc.)


The Solution
A good solution to this is to force Outlook to skip the Root domain completely – Optimizing the Outlook AutoDiscover process by skipping the root domain query. This article was written by a fellow MVP I know and I can vouch that this does indeed work in production and is not an unsupported configuration.
Further Notes
Do not expect this behavior to have changed in Outlook 2016. It has not. If you are planning an upgrade or reviewing your environment for issues, look to see if you have a DNS record that redirects your rood domain from http://domain.com to https://www.domain.com. This will cause issues for your clients down the road.
Further Reading
both of these links contain the process Outlook goes through to configure a mail profile:
AutoDiscover Behavior
Controlling AutoDiscover