The connection to the Microsoft Exchange Server is unavailable. Outlook must be online or connected to complete this action.
There is a simple solution for XP Pro users who encounter this message when trying to add their Ms Exchange mailbox to their Outlook. When configuring the mailbox for Outlook, after entering the server name, User Name and clicking on Check Name, Outlook will automatically replace the server name with it's fully qualified name. This is what causes the problem. Just set it back to your server name and you should be able to access your Exchange mailbox.
According to blurred_vision, XP Home users can connect to the server using the fully qualified name. I have not tried this as I'm not on XP Home at the office.
But then, I'm not actually using XP Pro either; I'm on Windows SBS.