O365 and Exchange 2016 recipient unable to receive internal emails

where your MX points?

Onpremise network?

In that case ensure that user have TargetAddress attribute set to useralias@domain.mail.onmicroosft.com and same email address is populated in user O365 mailbox properties under email addresses - it will get populated after AD sync runs

Then try

The best way to review adsync and after rerun hybrid wizard. But make sure user migrated is correct. As it might be not populated  correctly.

Another way.
As you are missing Exchange remote mailbox settings and the Exchange proxy address on on-perm server. The on-prem server doesn't know the mailbox was made since it was not populated  and the Exchange details are missing in the AD user object. Login to the on-prem Exchange server, use Exchange Management Shell and enable the remote mailbox and set the proxy address to the <user>@<domain>.mail.onmicrosoft.com proxy address that should be listed on O365.
The EMS command syntax is:
Enable-RemoteMailbox <Alias> -RemoteRoutingAddress <Alias>@<accountName>.mail.onmicrosoft.com

Can you try deleting the cached address and type only email address?
https://mso.harvard.edu/exo_config_outlook_cache
If it works you can add converted value as x500 address.
http://www.azure365pro.com/convert-imceax-ndr-to-x500-value-with-reference-table/
http://mostlyexchange.blogspot.com/2007/08/exchange-2007-legacyexchangedn-and-mail.html

Did my comment give you the clue ?

No it didn't the user was deleted and recreated before I looked at your solution.

Thanks to all of you guys