I recently upgraded my work PC to include Outlook 2003, (don't ask) and discovered that Outlook 2003 was painfully slow when doing any LDAP searches. This is actually a known problem with Outlook and LDAP lookups so lets get straight to the fix.

Add the follow to the registry:
[HKEY_CURRENT_USER\Software\Microsoft\Office\11.0\Outlook\LDAP]
"DisableVLVBrowsing"=dword:00000001
"NoDisplayNameSearch"=dword:00000001

Or you can just download the following file LDAPOutlookFix.reg (.36 KB)

Enjoy!