Warning - This user's on-premises mailbox hasn't been migrated to Exchange Online. The Exchange Online mailbox will be available after migration is completed.
Cause: This is because the user have on-premise Exchange mailbox or/and haven't migrate the mailbox to cloud.
Hybrid mode migration
1. Migrate the mailbox from on premise to cloud.
Direct cut over mode (greenfield)
Delete the user from O365.
1. Move the user out from the sync OU to non-sync OU on AD users and computers.
2. Resync the DirSync.
3. Make sure the user show under deleted users.
7. Force to clear the deleted users on O365.
Refer to this link.
8. Make the user under Deleted Users was deleted.
Remove the Synchronization of the user attribute to Office 365
1. Open Synchronization Service Manager (miisclient.exe)
2. Click on Management Agents tab, right click Windows Azure Active Directory Connector, select properties.
3. Click on Configure Attribute Flow,
4. Expend Object Type: User and Object Type: Group, search and locate for msExchMailboxGuid.
5. Select the mapping and delete.
6. Select Select Attributes, search and uncheck the msExchMailboxGuid.
7. Click OK to save the changes.
8. Repeat the step 3-7 for Active Directory Connector Agent. (for step 4, expand Object Type: User, Object Type: Group and Object Type: inetOrgPerson, search and locate for msExchMailboxGuid.)
9. Move back the user from non-sync OU to Sync OU.
10. Resync the dirsync.
If all users cannot create the mailbox, you might need to remove all the users from deleted users, and then reysnc all the user again from on-premise AD.