Question

Why are deleted mailboxes still appearing in the GAL (Global Address List)?

Answer

When on-premise mailboxes are disabled, there is a possibility of it still appearing in the Global Address List. This may be happening because the Exchange attribute that controls its appearance in the GAL is not replicated properly to Azure (Active Directory in the cloud).

In order to resolve this issue, you must first delete the MSOL user in Azure, and then remove it from the recycle bin. This will completely remove the object on the cloud side and allow it to be correctly recreated through the next Directory Synchronization. You can use the following cmdlets to do so:

Remove-MsolUser -UserPrincipalName [UPN]
Remove-MsolUser -UserPrincipalName [UPN] -RemoveFromRecycleBin