Delete mailbox and Global address book

When I create a users and mailbox or delete a user and their mailbox their name doesn’t show up in the Global Address Book. They can get mail if you type in their full e-mail address in Outlook. The can send mail; but their name is not in the Outlook Global Address book. Also when I delete a users and ask for his mailbox to be deleted it isn’t. Not marked for deleteion eoither and I have the setting to ) days to hold so it should delete. W2000 servers, Exchange 2000, Active directory, W2000 Domain controllers.

Why doesn’t their name show up in the global address list. Why won’t mailboxes delete? They get created.