Problem with Exchange5.5 on NT4.0.Some internal users can send mail to employee X, but not others?

Question

My company's Exchange 5.5 server is setup with the domain company-X.com, but recently has changed it to company.net. We are attempting to move everyones mailboxes so they receive at the new address.
One employee now can receive outside mail to [e-mail], but only one internal computer can send to [e-mail], and no one can send to [e-mail] message is:
Your message did not reach some or all of the intended recipients.

Subject:Test
Sent:2/7/2007 2:36 PM

The following recipient(s) could not be reached:

Employee on 2/7/2007 2:36 PM
The recipient name is not recognized
The MTS-ID of the original message is: c=US;a= ;p=IOA, Inc.;l=[Server]-070207193618Z-35
MSEXCH:MSExchangeMTA:[Domain]:[Server]

What am I doing wrong?

Additional:

There is one exchange server in the network. The users do not have automatic add to address book.

Something else, the user we're having problems with the login is djl, but the alias is dal.

I'm the IT person here, it's a small company with 10 employees.

Someone here who knows a little more of Exchange 5.5 than I has discovered that it's not the server, it's the Outlook clients. They are doing "automatic name resolution." They said to correct this in the past, they had to change something in the registry, start Outlook, then change the registry again. But he doesn't remember the exact key to change.

Answer 1

There could be a couple of forces at hand here...

1) People have the automatic add to address book feature enabled on their client. When they send or receive to an individual, it saves the address into their personal address book. Delete all the local entries and that might fix it.

2) If you have a multi-server environment, make sure your directory is synchronized. In Exchange Administrator, under your site, go to each server and get the properties page on the directory service. Then click update now. Do that at least 2 times per server, but switch servers each time you update.

3) In your internet mail connector, under the routing tab, you need to add company.net as inbound.

4) In your DNS configuration, your mx record for company.net needs to be set to your server address. (I won't go into the complications of firewall translated addresses and such, but if you have a competent WAN guy, that should all be okay)

5) Try creating a new test user with the correct parameters right off the bat. See if that works. Worst case, since you have 10 users, create 10 new users with the right info and copy the data over.

6) Did you monkey with the distinct names? That can make life somewhat miserable. For your users, you would only want to change the SMTP address and nothing else. Don't change site or organization names (will it even let you?)

7) Sometimes it just takes time. Usually not so much in a single server environment, but in a multi server environment, it can take a couple hours for everything to work itself out when you change stuff up.

8) Stupid answer, but have you considered upgrading to 2003/2007? Exchange 5.5 is WAAAAAY out of support, so it would be a good idea to get off of that before a catastrophy occurs.

9) You are adding the right SMTP address inside the e-mail addresses tab for each user, right?

I'll be watching this, if you have any further feedback, or you can e-mail me through here.