I have a user that changed her last name. The username is jyoung and was changed to jcamp. In Outlook 2002 when you send her an email the name pops up correctly as John Camp, but after that is says:
Everything looks fine in active directory including the alias, which is listed as jcamp.