After becoming unable to download identified updates in Windows Update, and also being unable to search for new updates, I did a detailed scan with Microsoft Security Essentials which identified and removed some malware
Since Windows Update still wouldn't work I restored my settings from last Friday with no improvement. Using Fix problems with Windows Update gets stuck on Fixing problem.
I then tried to do a reinstall as an update, but the installer was unable to find any updates (or rather it was forever* trying to locate any).
On a tip from a friend I looked in the hosts file but it was unaltered.
Does anyone have any ideas short of doing a fresh install?
*Forever is a relative term but in this case it's 90+ minutes.