Ok, this article fixed it for me. Not sure which server it was pointing to before but try this if you have similar problems. http://forums.msexchange.org/m_1800463281/mpage_1/key_/tm.htm#1800463281 This fixed the Outlook name resolution issue, not the pop up after Outlook connects though...

We are on Windows 7, and on new systems, Outlook 2007 doesn't connect to Exchange to resolve the user. I found this FixIt that seems to be the only thing that works http://support.microsoft.com/?kbid=319206 . I think the error message is "The connection to Micrsoft Exchange is unavailable. Outlook must be connected or on line to complete this action." We are on Exchange 2007 SP3 and DC is 2008 Standard x64. Also, on our domain, if you close outlook and open it, it asks for credentials. I'd like to get rid of this but nothing seems to work.