Context : Users of your SharePoint web applications can receive email alerts, but they are never notified by all the « My Site » activities, such as « Someone has started following you » or « Someone has mentioned you ».
In the SharePoint logs (ULS), you can see errors like:
Failed attempt x sending mail to recipients: firstname.lastname@example.org. Mail Subject: NAME Surname mentioned you in a conversation. Error: SmtpException while sending email: System.Net.Mail.SmtpException: Mailbox unavailable. The server response was: 5.7.1 Client does not have permissions to send as this sender
Solution : These notifications seem to be sent in an authenticated way, by the app pool service account (unlike the standard emails (alerts) that use the address defined in the « outcoming email » in central administration, in an anonymous way). So you have to add the right « Send-As » to this account in Exchange.
NB : If it doesn’t work, grant this right to the SharePoint Timer service account as well. I still have a doubt on this one :/
Source : Technet forum