Thanks for the tip. I am/was experiencing the same problem with users. Here's
the steps I found to resolve it for Outlook 2002:

Adding the Outlook Address Book service
For Outlook 2002:

1.      On the desktop, select Start > Settings > Control Panel. (If you're
in Classic Start Menu View)
On the desktop, select Start > Control Panel. (If you're in Start Menu View)

Note to see which View you are viewing Right Click on the Start Button,
choose Properties, Start Menu Tab then choose from either Classic Start Menu
or Start Menu.

2.      (In category view) Click on Other Control Panel Options.
Double-click the Mail or Mail and Fax icon. (If in Classic View)

3.      Click the Email Accounts button.

4.      Select View or change existing directory or address books and click
Next to see if you already have the Outlook Address Book service installed.
If it is, there is no need to continue. If it is not, click Back and continue
to the next step.

5.      Select Add a new directory or address book and click Next.

6.      Select Additional Address Books and click Next.

7.      Select the Outlook Address Book and click Next.

8.      Outlook 2002 should return to the original Mail Setup screen.