AND IT WORKED!
So in summary:
- You need to get a root shell in your currently installed Android flavour, either via permanent or one-time booting to a magisk image
- Run restorecon -FR /mnt/vendor/persist
- Reboot
As people have mentioned here and elsewhere MESSING WITH THE PERSIST IMAGE CAN BRICK YOUR DEVICE, so do this at your own risk!
I’m not sure if or how I could get into contact with the right people, but maybe this is something the default OS package should fix automatically? I won’t make a very hard argument for this, as it will probably only affect people who should be able to fix it themself now that this thread exist.
Thank you very much everyone in this thread!