Windows 7: Windows Update error 80072EFD

Already did that, the only bad thing is that I use to clean Program Files folder for uninstalled programs so now I have no idea which programs that were installed.

Actually I find Kaspersky really good, I think I'm going to stick with it. I've run both Kaspersky and Malwarebytes scans.

In that case, try checking the AppData folders in your profile. - you'll need to enable viewing of hidden files, and System folders/files

No AV leftovers in neither of the folders Local, LocalLow and Roaming as far as I can see. I'm not sure the anti-virus is the problem here though, I have a laptop on which I experiment with different security solutions aswell and there the updates works perfectly.

I'm by no means certain it's the cause either - but it's always the first thing that needs to be cleared up.

Now open an Elevated COmmand Prompt, and type

NETSH WINSOCK RESET

hit the Enter key, and reboot on request

retest WU

Still getting the error, I'm not sure but maybe there is something wrong with the actual Windows Update files. Is there anyway to reset/reinstall them?

I always like to do as much fixing as possible in a non-destructive way - but it does sound as if we may have to do something a little more drastic.

I'm assuimg here that you can accessall the normal sites - *including* www.symantec.com www.microsoft.com and www.mcafee.com without a problem, and that Kaspersky is happily updating itself?

Start by running Fixit 50123 from here Error codes

Reboot and retest

Then download Fixit 50202 from here... How do I reset Windows Update components? - NOT the popover one, but the one in the KB article.

Run it in normal mode first

reboot and retest

if you're still failing, run in Aggressive Mode
This will delete your Update History, but not the list of Installed Updates
reboot and test

Yeah internet is working perfectly (except being slow because our ISP sucks) and Kaspersky is updating.

Ran both fixes with reboots inbetween and tried Windows Update, didn't work. (Also rebooted and tried aggresive)

Now Windows Update is displaying "Last search for updates and last updates installed" dates to never. Is this normal?

Yes - that's because the history was cleared.

In Windows Update, click on Change Settings
change teh settings to Never Update.
click OK, and exit Windows Update
Go back into Windows Update
Click on Change settings
Change to Automatically Update
Exit Windows Update

Go back into Windows Update
now try a Search for Updates.

Still won't work, it did spend atleast half a minut searching though. But still displays error 80072EFD.

Maybe there is some service not running or got corrupt somehow? I really have no idea, just guessing.

What's more likely is that there's something else getting in the way - do you have a 3rd-party firewall running, or are you using the Windows firewall?
Have you EVER had ZoneAlarm installed?