Couldn’t delete this user because the account is synchronized with your on-premises servers. You can delete the user from your on-premises server.

But you already DID delete them from your on-premises server!

This is all covered very well in this KB article. But in a nutshell, if you delete something from your local AD, and are using DirSync or Azure AD sync, and it doesn’t get deleted from the online tenant, you can manually delete it this way:

  1. Grab the Microsoft Online Services Sign-In Assistant for IT Professionals RTW
  2. Grab the Azure Active Directory Module for Windows PowerShell
  3. Open the power shell and run this to store your credentials

    $msolcred = get-credential

  4. Then run this to connect to Azure

    connect-msolservice -credential $msolcred

  5. Now that you’re all linked up, run this to remove that nasty orphaned object
    Remove-MsolUser –UserPrincipalName [email protected]
  6. All set!

note, there are also Remove-MsolContact and Remove-MsolGroup cmdlets for those purposes.