Most of LDAP clients (including the Microsoft Outlook products) contain a setting specifying the Directory subtree that should be used for search operations. In Outlook Express, this setting can found in Tools->Accounts->Directory Service, on the Advanced stub. It is called Search Base and it should contain the DN for the user domain (by default, that DN is cn=domainname).

If this setting field is left empty, Outlook products silently replace it with the c=country_code string, and search operations fail (unless your Directory has the c=country_code subtree).

If you do want to search the entire Directory with an Outlook product, enter the word top into the Search Base setting field.