I struggled for 2 hours with a Windows 2008 SP 2 machine that refused to do anything other than presenting an 80072efd error when asked to perform a Windows Update check. It worked two months ago. Nothing has changed to the best of my knowledge. I tried all the MS KB's. Nothing helped.

So when I merely changed Update Frequency to Install Updates Automatically and checked again, it suddenly started working. WTF?

PS: Seems like this was just a fluke. The real problem was that even though I removed the old (invalid) proxy server definition from IE, it still lingered in

HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Internet Settings\ProxyEnable

Once I set that to 0, and restarted both the BITS and Windows Update services and reinstalled Windows Update Agent, things still did not work. I proved that it was the proxy settings as once I set up a proxy on the address it was complaining it could not connect to, everything started working. So how do you clear a stale proxy? No idea.

Here is proof:

C:\Windows\System32>reg query "HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Internet Settings" | find /i "proxyserver"

C:\Windows\System32>netsh winhttp show proxy
Current WinHTTP proxy settings:
    Direct access (no proxy server).