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:
Default information
we added our SharePoint server IP’s
Authentication settings
And the following permissions groups.
We have added the FQDN of the exchange server in the outgoing mail settings for SharePoint.