One of our users was getting an undeliverable message error in Outlook 2013 warning that one of the recipient's email addresses was "no longer valid" when sending mail to another particular user within the company.
The recipient was able to still receive the emails regardless, and the sender did not receive the error in the Outlook Web App.
This lead me to believe it was something local to the Outlook client, particularly related to the Autocomplete.
Tried removing the recipients address from the Autocomplete list to no avail.
After some research, tried this and it worked.
For Windows 7:
Turn off Outlook.
Open widows explorer and turn on "show hidden files"
Go to C:\Users\**USER**\AppData\Local\Microsoft\Outlook\Offline Address Books
and re-name the f[older] here (add "old" to the end).
Restart Outlook.
The user was then able to send mail to the recipient without the warning message. We re-downloaded the Global Address Book and they were still able to send mail to the other user without error.
Source:
https://community.spiceworks.com/topic/397609-weird-email-issue-e-mail-address-is-no-longer-valid-using-office365?page=2