To get the users removed i did the following:
Uninstalled Azure AD Connect from the AD Server.
Then i installed to apps to connect to O365 Powershell
Install Microsoft Online Services Sign-in Assistant:
http://go.microsoft.com/fwlink/?LinkID=286152
Install the Windows Azure AD Module for Windows PowerShell
http://go.microsoft.com/fwlink/p/?linkid=236297
Once installed open and run:
Connect-MsolService
Somewhere it asks for a password. Type a O365 Global admin password.
Set-MsolDirSyncEnabled -EnableDirSync $false
Once done you can confirm the setting with:
(Get-MSOLCompanyInformation).DirectorySynchronizationEnabled
Now give it some time. 20min or so.
You can go to O365 Users and delete all your synced users.
To enable your AD Sync you can run this command again:
Set-MsolDirSyncEnabled -EnableDirSync $true
Now you will need to give it some more time. Was told 72 hours then it should start Sync again.
Mine took about 4 hours when i noticed the users are back on O365.
Now i opened Powershell on my Onprem AD Server and ran the following:
Start-ADSyncSyncCycle -PolicyType Initial
This will synchronize the objects back from AD to Office 365.
To check if the sync completed you can open "Synchronization Service"
This can give you some more info on your sync.