You will be faced with the following error if you try "Couldn't delete this user because the account is synchronised with your on-premises servers. You can delete the user from your on-premises server." this is fine to resolve if your domain is up and operational, you simply delete the account from AD and force a sync with AD Connect.
In this scenario this was my lab and the Active Directory that was destroyed ages ago when an SSD failed in my lab server.
It is possible to break the relationship to Active Directory if AD Connect is offline and the domain is unrecoverable. It starts by connecting to Office 365 using Powershell.
You can download the Azure AD Powershell module using the following command
Install-Module -Name AzureRM -AllowClobber
You can then connect to Office 365 using the following command
Connect-MsolService
When you are connected to your tenant issue the following command to disable directory sync
Set-MsolDirSyncEnabled -EnableDirSync $false
Once this command has run, it takes a while to propagate through Azure AD.
Once it was done you should be able to manually delete objects from the Office portal.
You need to enable directory sync again if you plan to provision a new domain and install AD Connect.
Set-MsolDirSyncEnabled -EnableDirSync $true
I managed to delete all the orphaned user accounts with the exception of one, the AD sync account. It failed with "We couldn't delete this account: Sync_rbVM. This is your directory synchronisation account and you'll have synchronisation failures if it's deleted."
After leaving the portal for a bit and trying again I managed to remove this account.