Deleted and Re-Added Exchange User Failure to Send

One of our users was having exchange difficulties so I got the bright idea of moving their messages off to a PST file and then deleting their profile and making a new one then transferring the messages back. It all worked out great and it even seemed to fix some problem, but now if anyone replies to a old email there is a send error as exchange can't seem to find the user anymore despite being setup with the exact same name/email. Is there a way to add some kind of alias or something that would fix this problem? My guess is that there is some kind of unique identifier that wasn't duplicated but I really don't know.

I have access to their account before it was deleted. So I can look up settings.

The legacyExchangeDN may have changed. This is the address that outlook is holding on to in the old emails, as well as the cached address book entries that are autofilled when they try to email the person. You can add the old value which looks like this:

/o=Organisation/ou=Administrative Group/cn= Recipients/cn=Username

back to their account as another x500 address (some of that is shown here):

http://www.simple-talk.com/sysadmin/exchange/exchange-e-mail-addresses-and-the-outlook-address-cache/

You'll have to get the old legacyExchangeDN (x500) address, which I think comes back to you in the bounceback you get when someone replies to the old account. It should say something like "couldn't find "/o=Organisation/ou=Administrative Group/cn= Recipients/cn=Username" ... Just add that to their account. Maybe the new mailbox is in a different group or something so the legacyExchangeDN changed...