We have a user which has somehow added a proxyAddress (an email address to their account) but they don’t have an Exchange Online mailbox, and seemingly never have. Microsoft says the following about it from thisĀ article:
mail and proxyAddresses are both email-related properties. The proxyAddresses property is a collection of addresses only relevant to the Microsoft Exchange server. It’s used to store a list of mail addresses for a user that are tied to a single mailbox. The mail property is used as the user’s email address for various purposes including user sign-in and defines the primary proxy address.
Both mail and proxyAddresses can be retrieved through the GET user API. You can update the mail via the Update user API, but can’t update proxyAddresses through Microsoft Graph. When a user’s mail property is updated, it triggers recalculation of proxyAddresses and the newly updated mail is set to be the primary proxy address, except in the following scenarios:
- If a user has a license that includes Microsoft Exchange, all their proxy addresses must belong to a verified domain on the tenant. Any that don’t belong to verified domains are silently removed.
- A user’s mail is NOT set to the primary proxy address if the user is a guest and the primary proxy address contains the guest’s UPN string with #EXT#.
- A user’s mail is NOT removed, even if they no longer have proxy addresses if the user is a guest.
proxyAddresses are unique across directory objects (users, groups, and organizational contacts). If a user’s mail property conflicts with one of the proxyAddresses of another object, an attempt to update the mail fails, and the proxyAddresses property isn’t updated either.
An example of the problem can be seen below, as you can see the object on the right has the bob@address.com email address but an incoming synching account also has this address. So we need to remove the erroneous entry (email address) from the account on the right, so the synchronisation happens properly.
Of course, how can you end up in this situation? Well, there are a few ways, it could be an account that did have a mailbox but it has now been removed and the associated address was not removed, or in this case the user had an administrative account which they edited the profile of to add their on-premise email addresses to so it could receive email, turned out when editing the profile, this gets the email addresses stuck in there.

When we look at the object, we see the SMTP address (circled).

Resolution
To resolve the issue, we need to add an Exchange Online licence to the user’s account, once added, we can then remove the problematic proxyAddress, then we can remove the Exchange Online licence.
Add a Licence to Enable Mailbox Features
Add the licence, Microsoft 365 E3 should do the trick (or whatever you are using in your environment), then click on “Save Changes”.

Remove Problematic Address
Using PowerShell run:
Connect-ExchangeOnline
Set-Mailbox "Bob Smith" -EmailAddresses @{remove="bob@address.com"}
Where bob@address.com is the email address you want to remove.
Note that if the problematic address you are removing is the PrimarySMTPAddress, you need to add something in its place BEFORE you attempt to remove the problematic email address. So, you’ll need to add something unique.
Now run the following command to see that it is gone!
Get-Mailbox "Bob Smith" | fl DisplayName,PrimarySMTPAddress,EmailAddresses
Remove Licence
Finally, we remove the licence, we added earlier from the user account, then click on “Save Changes”.

The issue should now be resolved, also check to ensure you don’t have multiple things that are conflicting!