Nach tagelangem Ausprobieren und dank der Hilfe des Sysnative-Forums hat es endlich funktioniert, das Windows-Update zu installieren!
Das gesamte Problem bestand aus genau 2 fehlerhaften Dateien, durch die ein fehlerhaftes .NET Framework nicht deinstalliert werden konnte, dessen Existenz wiederum den Update-Fehler verursacht hat. Also ziemlich viele Ecken, um die man für die Problemlösung herum musste.
Im Detail waren das die Dateien "C:\Windows\Microsoft.NET\Framework\v2.0.50727\CONFIG\machine.config" und "C:\Windows\Microsoft.NET\Framework64\v2.0.50727\CONFIG\machine.config"
Den Inhalt der beiden musste man durch den Inhalt aus der jeweiligen Datei "machine.config.default" ersetzen. Dann das Paket "NetFx3" deinstallieren, den PC neu starten und letztendlich das Windows-Update erfolgreich installieren.