So You see this error in NDR when the message bounces back. In my case I had a normal AD User with mail-attribute populated. Exchange figured out that this user has a mailbox inside the organization. It wasn't. The user is located in local AD, but is only synced to Office 365, no local mailbox provisioned. So the fix is, add TargetAddress -attribute to the users with the same mail-address that they have. And below is the script for it. 
Get-ADUser -Filter {UserPrincipalName -like "*@whatever.fi"} -Properties * | ForEach-Object { $_ | Set-ADUser -Replace @{'targetAddress'="SMTP:$($_.mail.Trim())"} }
You can also use different filters, but I used UserPrincipalName. Happy Powershelling,

Archives