We performed an upgrade from Exchange 2000 to Exchange 2010 and migrated the user mailboxes by exporting to PST and them importing them into Exchange 2010. The new Exchange 2010 is in a different AD Domain than the Exchange 2000 server was. All the users were manually recreated in AD on the new domain.
A lot of the users were getting the following errors:
The e-mail address you entered couldn't be found. Please check the recipient's e-mail address and try to resend the message. If the problem continues, please contact your helpdesk.
After searching a bit I saw this might be related to the Offline Address Book or the Nickname file in outlook on the local machines. We deleted all the NK2 files and refreshed the OAB.
The users continued to get the errors prompting us to setup an X500 address for each user in Exchange:
/O=THEDOMAIN/ou=FIRST ADMINISTRATIVE GROUP/cn=Recipients/cn=user5
After doing this the users get a different error:
You can't send a message on behalf of this user unless you have permission to do so. Please make sure you're sending on behalf of the correct sender, or request the necessary permission. If the problem continues, please contact your helpdesk.
Hoping someone has a quick solution for these issues.