Delivery has failed to these recipients or groups:
Fake Name <mailto:email@example.com>
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.
A user gets the above message (I replaced real name with Fake Name, that's the recipient's name) after they try changing the "From" address to an address they have full Access and Send permission access as (granted in the Exchange console).
However, they do not get such an error message if they specify the same "From" address by choosing "From" button and then "other address" and selecting the e-mail from their local contacts (I added it to their local contacts).