Phantom Account

We had a very similar case. I have found a strange address in our global address book, which actually had a typo in it, so at first i thought emails go nowhere. But once i have typed the correct address, say company@domain.com, it actually forwarded the email to another user user@domain.com. Nobody new what was this address, nor that user, nor me. Maybe at some point somebody was experimenting with forwarders. Anyway, this SMTP address existed, but no user tied to it (not in local AD nor ir Azure AD).

get-mailbox -identity company@domain.com was returning result with user@domain.com in ForwardingSmtpAddress line.

But trying to delete that mailbox with PermanentlyDelete switch gave error that user still exists, although it couldn't find the user. With the help of MS support we were able to remove it finally.

Everything was done via PoweShell. It went like this:

$UserCredential = Get-Credential
$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection
Import-PSSession $Session
Connect-msolservice
$a = get-msoluser -all  
$b = get-msoluser -all -returndeletedusers  
$c = get-msolgroup -all  
$d = get-msolcontact -all  
$e = get-recipient -resultsize unlimited  
$all = $a+$b+$c+$d+$e  
$search = "company@domain.com"  
$all | ?{$_.emailaddresses -match $search -or $_.emailaddress -match $search -or $_.userprincipalname -eq $search -or $_.proxyaddresses -match $search}
remove-mailbox -identity company@domain.com

Not sure why it didn't work with simple remove-mailbox command. But it was removed and disappeared from global list, so the ticket was resolved.