One machine on our NT 4 network (using Exchange 5.5 and Outlook 2000) cannot start Outlook. The error message is always along the lines of "Network Problems are preventing connection to the exchange server."
However, this machine can connect to the server that Exchange is located on, browse it, etc. Office has been reinstalled and the user's profile works fine on other machines.
Why does Outlook insist that the Exchange server isn't available, when it is?
First thing I'd do is drop to a command-prompt and make sure you can ping that Exchange server by name. ("PING YOUR_EXCH_SERVER")
You don't mention if you're using roaming profiles or not. If not, I'd create a fresh new profile for this user on this machine, just to make sure that you're pointing at the correct Exchange server and that there are no typos or other problems in the server name.
You also don't mention whether there's anything unusual about this machine, such as being behind a router or connecting remotely. Remember that Outlook and Exchange use Remote Procedure Calls (RPCs) to connect. Just because you can connect via Network Neighborhood is no guarantee that you're getting your RPC connections right.