Try reading this article:
"Troubleshooting Check Name Errors",
I bet it will solve your problem!
Blog "subject: exchange"
"Derek" <Derek@discussions.microsoft.com> wrote in message
> When i create a new user, they are not placed in the global address list.
> have forced replication, im not using a cached copy of outlook, i have
> days without them showing up.