Yes, I found a solution
- Create Windows 11 Installation Media on USB - Download Windows 11 (microsoft.com)
- Click on setup.exe from the USB
- Do an install keeping apps and files.
When the install was finished indexing worked great.
One thing I did before the install was to remove all the indexing locations (until "index these locations" is empty) and the click 'rebuild'. I did this to clear any previous indexing information. I have no idea whether this actually does anything but if you want to ensure you do exactly what I did maybe do this as well.
Since then, the PC has been fine. It indexed all of my emails and files in 4-5 hours.
Thanks again for this workaround, it saved me pulling some hair out. Unfortunately like mentioned later on, I am running into the issue again a week or so later, seems like indexing rather quickly cannot keep up with moderately-sized changes to the filesystem (e.g. uninstalling large apps...). At least it's better than before.