Eliminé los registros de regedit, pasé Malwarebytes’ Anti-Malware, el problema persistía.
Volví a formatear y ya no ha vuelto a salir, y sólo ha habido un cambio. Habían conectado un ratón USB de publicidad de farmacias!
El culpable de que reapareciera después de cada formateo el virus era el ratón, que lo habían conectado al equipo sin mi visto bueno (se jodió el ratón viejo y dijeron, pues usamos el que nos han regalado). Ha sido formatear sin ratón y usando un ratón normal, y ya no ha vuelto a aparecer.