I posted a similar question yesterday to the guys over at
microsoft.public.exchange.setup as well, to maybe attack this issue from an
Exchange server perspective. Maybe the folks over here can offer some
insight, as this may be a client issue.

I have a new Exchange 2007 server. New Outlook 2003 clients can connect just
fine. Outlook 2007 clients tested on both XP and Vista, fail. The error I'm
seeing is:

"Outlook cannot log on. Verify you are connected to the network and you are
using the proper server and mailbox name. The connection to Microsoft
Exchange is unavailable. Outlook must be online or connected to complete
this action."

and then

"The name cannot be resolved. The action cannot be completed."

Everything with the domain is good. AD, DNS resolution, OWA. Also, existing
Outlook 2007 clients are working just fine. Only new Outlook 2007 clients
can't connect. Could anyone offer an insight as to why this might be
happening?

Thanks, PC

I get the exact same issue, only with Exchange 2003 and outlook 2007
clients. The client really doesn't even try to resolve the name
becuase I get the same result even if I give it a bogus exchange
server name.