OK, so here's what I found. Method 2 did not work, as you know. Method 3 (SFC.exe) we have done before, and you said it was not helpful. I ran it again just to be safe. I did Method 4, no luck.
Method 5 was interesting. It said to go to HKEY_LOCAL_MACHINE\COMPONENTS, but I could not find that directory. I check in the other HKEY's, but COMPONENTS was nowhere to be found. I don't know if that is because the KB article is written before Windows 7 or what. So Method 5 did not happen.
Method 6, no change. Method 7 is apparently not relevant in Windows 7, as the excluded folders don't exist. Method 8 was skipped. Method 9 did not help.
Method 10 was another interesting discovery. I tried to manually start Windows Update, and it said that it could not start because the service was not started. I opened services, and the service IS started. I restarted it to be safe, but it did not help. I don't know if that info helps or not. Method 12 I have done a few times now, so I'm not sure it is really worth doing again at this point.