OL2K3 automatic name checking

There is a name that I type into the To: field of a new message, and as the name shows up via the automatic name checking I notice that the alias(?) next to it is wrong. Let's say the person's name is John Doe. Normally I'd type in Joh and see something like John Doe <doejoh>. Well, instead of that I see John Doe <flopat>. Now I know that this person's account on the network was someone else's account who left. So when this new person came in the old person's account was simply renamed, the password reset, the alias was changed to doejoh on the Exchange General tab in AD Users and Computers, etc. Everything looks like it is setup correctly, but the alias in that automatic name checking option is the person's alias who left. I have renamed the .nk2 file that stores a cache of these automatic name checking names, but that had no effect. Anyone know of a way to fix this?

Have you also changed the e-mail address(es) for the person as well, and set the correct one for the new person as primary?

Good questions. I have changed everything I can find in this users AD account. I even went into e-mail addresses and changed the three different items in there to use the correct alias (there was the smtp address, MS, and X400). I just did this about half an hour ago so maybe it will take time for it to kick in if that will actually fix the problem? I don't honestly know.

It does take some time for the change to be effective unless you have changed the run interval for the RUS recipient update service.