A cloud-based identity and access management service for securing user authentication and resource access
Once you have restored the cloud user from the Recycle bin, you can overwrite it's ImmutableId with any other value, including null. Here's an example:
I specifically used the Graph Explorer above, as the PowerShell module has a known issue with setting null values. You can still use the Update-MgUser cmdlet to set any other value, much to the same effect for your scenario. For example:
Update-MgUser -UserId ******@domain.com -OnPremisesImmutableId "blabla"
If you must use PowerShell, try the Invoke-MgGraphRequest cmdlet instead:
Invoke-MgGraphRequest -Method PATCH -Uri "https://graph.microsoft.com/v1.0/Users/{userId}" -Body @{onPremisesImmutableId = $null}