So the second time this happened, I researched the problem and while I can’t find anyone who’s posted the exact issue of Outlook changing randomly, this community article seems to fit. Scroll down to the post by Ognyan Y. http://community.office365.com/en-us/f/158/t/45554.aspx
And because I hate it when links go dead, here’s a copy & paste of the suggestion (all credit to the original author!). I did indeed find a service connection point (SCP) in our Active Directory for an autodiscover of our old exchange server name, which I’ve now deleted. Cross your fingers for me that this does the trick!
“I think the problem is related with the Service Connection Point (SCP) in your local Active Directory. When Outlook starts the Autodiscover process he first tries to find the Exchange servers using this SCP and if he fails then it queries the DNS for the auto discover record. If you do not plan to use the local Autodiscover you can remove the SCP from the AD.
To find the SCP open Active Directory Sites and Services, then go to View – > View Services Node. This will show the services node in the console. Then see the screen shot where to locate exactly the SCP”