Here is my scenario. If I connect via VPN and configure outlook 2007 to connect to exchange 2007 using Outlook Anywhere, it works. When I disconnect the VPN, exit Outlook, and then re-run Outlook, it prompts me for my login credentials. I login and am able to connect and send/receive email. Everything seems fine.
However, If I try to add an account and connect with Outlook Anywhere with same exact settings but not through the VPN, it doesn't work. I can't create the account. When I go to "Check Name", a prompt displays for my credentials. I enter credentials and next screen goes to "The action cannot be completed. The connection to Microsoft Exchange is unavailable. Outlook must be online or connected to complete this action."
Any ideas?
For other looking to solve this issue, there is a bug with Exchange 2007 on Windows 2008 Server (I have R2 installed).
The workaround was to disable IP version 6 in the registry and then restart the server. I verified that ip 6 wasn't showing when issuing a ipconfig.
Outlook anywhere started working.