So I ended up uninstalling all the Steinberg software (I backupped the Cubase preferences), i.e. everything with Steinberg in the name in Windows Apps settings, plus the elicenser program.
I also manually deleted all the “Steinberg” folders inside my C: drive and reinstalled everything. Then I put the preferences back (but I had to delete the Mediabay files in C:\Users\ [my user name]\AppData\Roaming\Steinberg\Cubase 12_64).