Have had this with following conditions:

• User account is synchronized from local AD
• User used to have on-premises Exchange mailbox which have been migrated to Office 365
• Since then, user has left, Office 365 license has been removed but AD account hasn't been deleted
• User then returns, maybe it was just long leave or maybe re-hired
• You assign license back to user, no mailbox is generated, and you get this error.

Office 365 reads this info from users local AD account attributes. This error is because on-premises AD has or had Exchange Server at some point, and it was used to manage this user. Then users account in Office 365 lost some attributes when mailbox license was removed and later automatically cleared. If you still have an Exchange server, go check mailbox type for this user. If it shows “User” this error is correct, and you need to migrate the mailbox. If Mailbox type is “Office 365” or you don't have Exchange at all, then some AD Attributes need to be cleared:

1. Open Active Directory Users and Computers management, from View menu select Advanced Features. After this look for affected user and open Properties. Note that if you use find tool to find user and select properties, you are missing Attributes tab, you need to open users properties from tree view.

2. From user Properties look for Attribute Editor tab

3. Find if following attributes have values and clear them:

• MsExchMailboxGuid
• MsExchRecipientDisplayType
• MsExchRecipientTypeDetails

4. Go to Azure AD Connect server and run intial sync, from powershell: Start-ADSyncSyncCycle -PolicyType Initial

5. After while user Office 365 mailbox status should change to “Provisioning mailbox”

6. If you still have on-premises Exchange and want to manage user from Exchange, previous steps made user to dissappear from Exchange ECP. You need to re-provision remote mailbox from Exchange (this won't actually affect Office 365) to make it visible in Exchange management. From Exchange PowerShell, run command

''Enable-RemoteMailbox "Kim Akers" -RemoteRoutingAddress "kima@contoso.mail.onmicrosoft.com"''