The only thing I can find (others will be more helpful, maybe):

Either he rightly uses a LDAP (a remote directory/address book), but it isn't available somehow (then he should contact his LDAP-provider or system manager for support and check his settings) or somehow Outlook only thinks it should use LDAP while it shouldn't, because he only has a local Address Book and isn't part of a LAN. That should be in the settings also. Outlook can be tightly integrated with Exchange Server and the newer the version, the more integrated it seems to be.

I don't have Outlook 2003, so I can't check Outlook Help nor the Tools>Options.

For more information on Outlook and LDAP:

Hope this helps.