The cause appears to be relatively straight forward: this issue may occur if the user name is already used or if an existing email address that's based on the user name already exists. In this case licensing attempt will fail if the provisioning process determines that another object already has a user name or an email address that matches the user name that's being created.

I verified the issue, checked existing users and email aliases, but could not find anything that would explain the problem - none of existing users were using the mail address This email address is being protected from spambots. You need JavaScript enabled to view it..

Next, I connected to Exchange Online by using a remote Windows PowerShell session ...

$UserCredential = Get-Credential
$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection
Import-PSSession $Session

... and ran following command:

$DuplicateUser = "This email address is being protected from spambots. You need JavaScript enabled to view it."
Get-Mailbox | where {$_.EmailAddresses -match $DuplicateUser} | fl Name, RecipientType, EmailAddresses

Unfortunately, the command returned no results, dashing my hopes for quickly finding a clue, so I turned to TechNet forums for help. As a reader of this blog I suspect that you, like me, are a frequent visitor to TechNet forums. I have spent dozens of hours helping other people out, but this time it was my turn to ask for help. Within minutes, I received a recommendation to run a number of commands against Exchange Online / Azure AD. The key to solving the mystery lay in executing Get-Recipient cmdlet, which allows you to view existing recipient objects in your organization. This cmdlet returns all mail-enabled objects (for example, mailboxes, mail users, mail contacts, and distribution groups):

Get-Recipient -ResultSize Unlimited | where {$_.EmailAddresses -match "$DuplicateUser"}


Name                RecipientType
----                -------------
Christopher Blair   MailContact

It would seem that I had a contact in my address book with the exactly same proxy address as the user object I was trying to create. Confident I solved my mystery, I logged into the Exchange admin center, navigated to receipients / contacts tab and removed the contact object associated with the proxy address. I tried to create the user again and to my immense satisfaction, the provisioning process finished within a couple seconds. The case was closed! As to why the proxy address was already present in the contacts list, I can only assume that at some point I provisioned that user and then either changed user name or deleted the user object, but forgot to update or delete the contact.