We currently have two employees that worked for the company before then left. When they left, their Exchange 2010 mailboxes were deleted. When they came back new mailboxes were created with the exact same aliases and addresses as the old ones. Does that make sense?

The problem: If someone starts typing their name (the previous now current employees) and selects the suggested contact, the message will fail delivery. If the address is typed out completely without selecting the recommended, the delivery fails. If you choose the contact from the global address book, delivery works perfectly...

I'm so very confused.

Check their email addresses in AD. I am not sure the email is what you think it is.

The problem: If someone starts typing their name (the previous now current employees) and selects the suggested contact, the message will fail delivery. If the address is typed out completely without selecting the recommended, the delivery fails. If you choose the contact from the global address book, delivery works perfectly...

I'm so very confused.

The "suggested" contact is coming from the nicknames cache, which is stored on every client (as an NK2 file), or, in every user's mailbox. (it depends on the Outlook client version. old clients use NK2)

Every client needs to delete the nickname.

When the nickname is "suggested", use the cursor keys to select the suggestion and then press DEL.

(there might be another way, but I can't think of it righ

We currently have two employees that worked for the company before then left. When they left, their Exchange 2010 mailboxes were deleted. When they came back new mailboxes were created with the exact same aliases and addresses as the old ones. Does that make sense?

The problem: If someone starts typing their name (the previous now current employees) and selects the suggested contact, the message will fail delivery. If the address is typed out completely without selecting the recommended, the delivery fails. If you choose the contact from the global address book, delivery works perfectly...

I'm so very confused.

With the NDR, you can construct the correct X500 Address to add as an additional Address to the restored mailboxes and allow the Outlook cached entries to be delivered correctly.

http://blog.westurn.net/2013/04/convert-ndr-to-legacyexchangedn-x500.html