I was struggling trying to get Outlook 2007 to connect to my Exchange 2003 server...

Here is what I did.

I was trying to add a new user, but I continued to get a message that Exchange was unavailable or offline.  Yet, no one else was complaining and I could connect using OWA.   So I figured it was a problem with the client computer. 

Where it prompts to put in the Exchange Server name I put in the Domain Controller name instead.  This quickly resolved to the name of the exchange server and then I was connected.   I was able to finish setting up the new user.   So I could resolve the name by going to the DC instead of the exchange server.  Time to look at the services on the exchange server.  I noticed that the Microsoft Exchange System Attendant had stop running.  This is needed to resolve Active Directory information.    So if you run into this problem make sure this services is running.