Linked Mailbox and account rename

I had two users.  User One left and User two took over from the fist one.

User One was the master account as a linked Mailbox
User two had his own mailbox.

I deleted User Two and his mailbox
I renamed both the linked account, and the disabled account that are associated with the mailbox

Situation:
User One can now send from outlook, but the reply email address still shows that of the account PRIOR to the rename.
Other users can email user one from external and OWA, but not Outlook.  They get a 550 5.1.1 Recipient not found.

Done:
Double checked all accounts (EMC and AD)
Checked Alias
Checked email Address in EMC
Rebuilt Address book
Restarted Address book service, sys attendant, Exchange mailbox assitant

Any idea's what I missed ..... out of idea's

Thanks