You might experience this problem when sending mail via POP3 or IMAP while OWA works fine.
On Exchange Server 2010 you can try the following steps:
1) Go the the Exchange Management Console and select the user experiencing this problem. Right Click, go to the send as permissions option.. check that User NT AUTHORITY\SELF is listed. If not add it.
2) In Exchange Management Shell execute:
add-adpermission "ConnectorName" -User "NT AUTHORITY\Authenticated Users" -ExtendedRights ms-Exch-SMTP-Accept-Authoritative-Domain-Sender
3) In Exchange Management Shell execute:
Add-AdPermission -Identity "ConnectorName" -User "NT AUTHORITY\Authenticated Users" -ExtendedRights ms-Exch-SMTP-Accept-Any-Sender
4) If you get an error, it is necessary to remove the account or repair it within Outlook, or else the error will 'stick' until you do.
note: you have to perform steps 2 or/and 3 for both internal and external connectors.