I have a problem with the stuck Windows Update the second time around. First time I solved it by reinstalling Win7 from CD on top of my existing installation. Second time I did not want to go through the same thing. After trying probably 50 different things I found something that worked for me when nothing else worked.
The symptom of the problem is that Windows Update is stuck on "Checking for updates" screen and svchost process uses 100% of one core as shown in the task manager. After stopping the update service the process goes back to 0% CPU. The cycle repeats every time one wants to check for updates.
Nothing helped to solve this problem - native Windows troubleshooter, downloaded FixIt things, downloaded troubleshooter, deleting SoftwareDistribution folder or folders within it. After the next update check the system would get in to this state. What is worse this state preventing Security Essentials from updating as it uses the same Windows Update process.
The solution turned out to be running WSUS Offline tool and letting it install all of the missing updates. After that the issue appears to be resolved and Windows Update is working normally. There is some sort of dependency in important updates that causes this infinite loop in Windows Update service.
I generally do not install all of the important updates since I don't think that I need something like Croatian Time Zone fix. Clearly that is a mistake since there is something that is needed in important updates and skipping it makes Windows Update break.