We encountered this error (Mailbox unavailable) while setting up the newsfeed notifications for SharePoint 2013. We solved this by creating a receive connector in Exchange 2010 with the following settings:
we added our SharePoint server IP’s
And the following permissions groups.
We have added the FQDN of the exchange server in the outgoing mail settings for SharePoint.