We have a joint mailbox that users have access to for digital faxing. The users have both Full Access to the mailbox so that its contents are visible to them in Outlook, and Send As permissions, however when they attempt to Send As the fax e-mail account, they are getting a rejection message because they do not have Send on Behalf of permissions. We cannot just give them Send on Behalf of, because the efax service needs to see the e-mail as coming from the faxes mailbox, not on behalf of it.
If you're using Outlook in Exchange cache mode, your issue might be outdated OABs. I've run into this exact behavior before and the solution was to force Outlook to download new OABs by deleting the existing ones normally located in C:\Users\$username\AppData\Local\Microsoft\Outlook\Offline Address Books\