“Suggest name while completing To..”

I have Outlook 2003 running on the workstations and Exchange server 2003.
Recently one of our employees quit (call him “John”) and a replacement was hired (call him “Steve”). I renamed John’s mailbox to Steve. The problem is that when the rest of the office tries to send him email, the autosuggest feature is showing “Steve“. Steve is getting the email message, but is there a way to get rid of “John”?
Thanks