Exchange 2010 Removed user and re-added account. Now internal e-mails bounce.

Hello,

I removed a users e-mail account from Exchange 2010  (Actually clicked remove from Exchange Console)

I re-added all accounts (AD, E-mail)exactly the same name, reloaded the e-mal from a .pst and everything appeared to be working correctly.

Yesterday I got a call saying that the users e-mail address was sending bounceback messages. After testing it looks like external e-mails are working but internal e-mails are being rejected.

I added an X500 address to try and resolve the issue but have had no luck. I am stuck at the moment and am trying to brain storm.

I was thinking that it could possibly be the .nk2 file on all of our users computers that had the name saved, but since it is the same and nothing changed wouldn't it work?

Any help would be greatly appreciated.

Thanks!