Even after being granted the Full Access, Send As and Send on Behalf Of rights, my emails from that user account were being rejected with the following error message:
Delivery has failed to these recipients or distribution lists:
You are not allowed to send this message because you are trying to send on behalf of another sender without permission to do so. Please verify that you are sending on behalf of the correct sender, or ask your system administrator to help you get the required permission.
This was a rather silly error. When creating a new mail, I was typing in the email address into the "From:" field of the new message. That is, I was typing in the full email address in the form of "emailAddress@mydomain.com". To send as the user, you need to either click the "From:" button and select the user from the address list or type the users Alias and let Exchange resolve it (E.g. emailAddress without the "@mydomain.com" part --> click Check Names).