So, ein kompletter Scan inklusive Bootsektoren, Registry und Rootkits war ohne Funde.
Ich habe inzwischen auch mal gegoogelt (und dabei dieses Thema gefunden...) und dabei eine Problembeschreibung entdeckt, die mit meiner identisch ist. Interessanterweise stammt sie aber von 2003. Lösung gab es natürlich nicht.
Edit: Gelöst (zumindest vorerst)!
Es handelt sich wohl um einen (auch bei MS) bekannten Fehler von XP. Nicht sofort, aber auf jeden Fall irgendwie hat bei mir geholfen, den SSDP-Dienst zu deaktivieren. Der PC wartet recht lange beim Willkommensbildschirm, aber die Symbole sind wieder da. Mehr findet man auf
dieser Seite.
Edit²: Wäre schön wenn das geholfen hätte.