As the user accounts are still synced we must extend the AD schema to add additional Exchange properties that can be synced to Azure AD.
First find an install on the MS site for latest Exchange, you don't need a license as you're not actually going to install it.
Extract the package using 7-zip or similar into a folder.
Run the setup.exe with the following parameters on a domain controller with a user account that has admin privileges:
Setup.exe /IAcceptExchangeServerLicenseTerms /PrepareSchema
This will add the extended Schema, you may need to wait for all DC's to sync or user repadmin to force a sync.
A few quick powershell commands to set the parameters to hide old users from the address lists (after you have renamed them and set their emails to a none default domain, we use the test onmicrosoft.com one)
Set-ADUser -identity zzzzz -Add @{msExchHideFromAddressLists=$true}
Use the short login name for identity.
Once AD is synced to Azure AD you should find that the users mailboxes (we convert to shared mailboxes) are now set to not show in address lists.
You may need to Refresh the Directory Schema in your Azure AD Connect after installing the Exchange Schema and run a full sync. (Still seems to be issues here with it not synchronising, still investigating and will update ASAP)
UPDATE: You need to specifically add the hide from address lists schema to the AD connect profile for it to sync, otherwise it'll ignore it.