Exchange amd Global address book

I have a W2000 network. A W2000 Exchange server. Active directory. 2 Domain controllers. I create a user in AD and they show up with all the normal properties, they get a mailbox created in the Exchange store, they have properties under the exchange tab BUT when I try to send them an e-mail the are not in th global address book in Outlook. It has been 5+ hours and nothing. I recently demoted the First Domian Controller that created the domain and have found no problems until now. It is strange because AD created a mailbox in the store but it doesn’t show on the global address list???

Ideas????? Be specific please