To add to the puzzling behaviour:

In running Win Update on my Win 7 Home Premium computer, I have encountered the slow scan behaviour that many hove complained about.

Following Susan Bradley's Patch Watch last week, I wanted to install first the KB 3161664 patch by itself, as suggested. I started Win Update to select it, and initially got an 'up to date' message, clearly in error since I had not run update since last month. So I downloaded the standalone package from the Windows Download Center. When attempting to run the .msu file, I got the 'searching for updates' message! Since the search was not necessary in this case, I changed the update setting to 'Never check ...', as suggested in several Internet discussions of this problem, since I already had the installation package. The update proceeded to install normally.

After restarting, I then ran WU to install additional patches. When the program started up, I immediately got the list of available updates. Not thinking about this, I changed the update setting back to my normal 'check but ...' setting, and restarted WU. I then got the 'searching for updates' message, which continued for some time. So I stopped the program and switched back to the 'Never check ...' setting, got the list as before, and proceeded to update selected hot fixes, successfully, as far as I could tell. So, in my case, changing the update setting appears to solve at least part of the slow scan problem.

(However, in checking WU operation today for this note, the available updates list was immediately displayed; perhaps the slow scan behaviour has been addressed since my experience last week.

Hoping that this might provide some more information.