The correct way to provision new users in Office 365 is to create new Remote Mailboxes.
If a Remote Mailbox isn’t present or has been accidentally deleted, you can create one and link it up to the Office 365 mailbox.
We can resolve this manually by completing the following steps:
From the Exchange Management Powershell (On-Prem)
Enable-RemoteMailbox username –RemoteRoutingAddress alias@domain.mail.onmicrosoft.com
Get the Mailbox GUID of the Office 365 mailbox (O365 Powershell)
Get-Mailbox –Identity emailaddress | fl Identity,ExchangeGUID
Copy the Mailbox GUID and place this into Exchange Management Sell (On-Prem)
Set-RemoteMailbox username –ExchangeGUID "GUID Copied from Last Step"
After you have completed these steps you should force an AD synchronization from DirSync