This can happen if you have users type mailbox without belonging to mailbox database
To find those users, execute powershell command :
Get-Mailbox -arbitration | Select Name, Database
This will show you the problematic users. You can fix this by add the users to database executing for each user :
Set-Mailbox "user name from the command above" -Arbiration -Database "Mailbox database name of your choice"