This just recently happened and I'm not quite sure what could have caused it. Whenever I now set up a new computer at the office, I log on with that user and start Outlook. Previousy the mail profile is set up automatically when first starting Outlook. But now, I get the error message "Connection to Microsoft Exchange is not available"
But if I click OK I get the option to control the server settings and the username. And strangely if I replace the server name with the actual IP address for the email server, it gets the username immediatly and everything is all well. Also, the IP address for the server name is then replaced with the exact same server name as it was prior to entering the IP address, only the server name has an underline in it.
I though, well this has to be a DNS issue but I don't think so as well. The DNS lookup looks just fine and there are no multiple DNS entries for that server name.