I finally solved it for me. It was Comodo after all.
I found it suspicious that 3 people in this thread seem to be using it, so I tried again and uninstalled it more thoroughly. Here are the steps I took:
- I backed up my Comodo settings (General Setttings > Configuration > Export), mainly for HIPS.
- I disabled my internet connection by disconnecting the Ethernet cable.
- I uninstalled Comodo using the "I want to permanently remove it" option.
- I rebooted Windows. My browser tried to open a Comodo website, so I checked for startup processes/services (w/ CCleaner), disabled these and rebooted again.
- I removed old VirtualBox traces (preferences, registry, caches and certificates, as described in the OP), then rebooted Windows again.
- I installed VirtualBox 6.1.18 in the default location while unchecking "Host-Only Networking", then rebooted Windows again.
- I opened the VirtualBox GUI and created a host-only adapter (File > Host Network Manager > Create). It went smoothly and Device Manager instantly displayed the adapter as functional.
- I rebooted Windows again, it still showed as working.
- I restored my old VirtualBox settings (Users\Username\.VirtualBox folder) and it still worked.
- I reconnected my ethernet cable and reinstalled Comodo, then restored its settings.
- I rebooted Windows again, the adapter still showed as functional. Even creating new ones worked without issues now.
- I reinstalled Genymotion (Android emulator which I use for the VMs I had issues with). During installation it created two new host-only adapters (which it never did before). Still, after restoring my settings there, everything worked without issues.
Apparently I half-assed the Comodo uninstall last time. I would guess the extra reboot steps were the crucial change. Or maybe I used the wrong uninstall option for Comodo the first time ("
I want to reinstall it", which also removed it, but maybe not completely?). I can't confirm if any of the VirtualBox based steps were necessary, I just wanted to cover all bases in one go and this sequence of actions did the job.
In the end I feel kind of dumb for how basic the solution was in the end. I simply did not expect Comodo to still interfere in some capacity while it was completely disabled (not in autostart, reboot, no obvious process running).
Thanks everyone for the help! I hope this solution works for you, too.