This appears to be a Known Issue with a Release In Progress. The link documents a workaround.
Some customers experiencing issue sending emails using Email-To-Salesforce due to PRVS implementation
Summary
Some customers may have a email security mechanism implemented on their outgoing mail servers called "Bounce Address Tag Validation" (BATV). The mechanism determines whether the bounce address specified in an email messaged is valid.
Essentially, this method prepends following in envelope-from field of
the email header:
(XXXXXXXXXX = numeric unique identifier)
Now due to a recent change on Salesforce side, our application servers
are currently rejecting emails where the envelope-from in the email
header has an email in the above format if an email is sent to E2S
email address.
Repro
If a customer (on NA8) sends an email to their E2S email address
or using Salesforce for Outlook Add Email button they may get a bounce
back message with content similar to below:
emailtosalesforce@a-xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.c.le.salesforce.com (Undelivered): 551 Failed due to: SenderAuthorization
Workaround
Currently, the workaround is to add your email address in
PRVS format under Email-To-Salesforce, My Acceptable Emails setting:
Setup | Personal Setup | Email | My Email to Salesforce
For example:
Actual email: [email protected]
PRVS email: [email protected]
Note: The PRVS format can be retrieved from your email headers
envelope-from or you can consult your internal IT to get the correct
PRVS format email.