Everytime I tried to check for Windows updates, I was only shown "Restart your computer to install important updates", though I already had restarted the computer several times.
At last I found the culprit: In the registry under [HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\WindowsUpdate\Auto Update], there was a key tellingly named "RestartRequired" (and otherwise empty). As soon as I had deleted that and checked updates again, I was shown a long list of updates.
Simple as that. As to why it hadn't been deleted: search me.