At my shop, we've employed Active Directory (AD) to negotiate access to all of the services available on the network. Although it can be a headache to set up, it really does make security nice and tidy in the long run. For example, if you want, you can use your AD to replicate security out to your wireless network adapters via RADIUS.
This weekend, I moved everyone from a POP-based mail server to an Exchange 2007 hosted service. The move was based on pain we were having with timely delivery of mail, as well as not having a SPAM block on the front-end of the server. I.e. when I would get email via my phone, it would download 200 pieces of SPAM along with my 15 important emails. Not a good solution.
Since I made the decision to migrate the company, I chose to be the guinea pig for the migration. I already had Outlook 2007 running, so I closed Outlook, changed my email account (via the control panel) and walked through the Exchange Autodiscover process without issue. Once complete, I merged my old PST files and within 30 minutes was up and running. It was all impossibly simple.
That is, until I started the process in earnest with the other employees. On the first install, I deleted the existing account, told Outlook I wanted to use Exchange and proceeded through the Autodiscover process. This time, however, there were various challenge-response boxes (that I didn't recall happening to me) and upon completion, Outlook complained with the following error:
Unable to open your default email folders. You must connect to your Microsoft Exchange server computer with the current profile before you can synchronize your folders with your offline folder file.
After going through the process a few more times, I realized that the clue I missed was the above-mentioned challenge-response boxes. When I paid attention, I found that both the local AD and the remote server were looking for authentication tickets. While I don't know what exactly was happening under the covers, my best guess is that the local network was attempting to pass along networking rights and was failing miserably, as would be expected.
So, if you're having this issue, the resolution is very simple. When you create a new Exchange email account, do not allow Autodiscover to run by checking the box at the bottom of the first screen that says, "Manually configure server settings or additional server types."
At this point, you'll need the FQDN for the Exchange server and the principal name. The FQDN you'll use in the first screen you get to after supplying your username, email address and password (as seen at the right). To set the principal name, click on the "More Settings" button on that next screen, then click on the "Connection" tab, then the "Exchange Proxy Settings..." button. You will find yourself at a window that will look like the following:

It might be easiest to get one machine to Autodiscover correctly then just copy these settings rather than attempt to wade through your provider's help, but if you have the information handy, it just takes a few seconds and you'll be up and running.
You may also want to experiment with the "On fast networks..." setting. In my network, it does feel much snappier, and was a suggestion by my host to improve Outlook startup and polling times.