I just added a second domain tree to my AD. I ran MS Exchange 2003 domain prep in the second domain. When creating accounts in the new domian everything looks like it is working I select the exchange server and storeage group but the account never shows up in the mailboxes, and the account in AD dose not show up with an email address in the general tab, and the email address tab is blank no address are in there. All other exchange tabs look correct and good. I also added the new domain name to the RUP. Not sure what is going on if the domain for some reason dose not haverights to create the physical mailbox on the exchange server, the new domain thinks everything is fine.

You have to add your domain to the Recipient Update Services. Also this error might happen if you don't have WINS server IP address in the properties of network adapter.

It is added to the RUS, and we don't use WINs at all.