BITS service is not starting, Windows Update always stuck at 0%

Windows update is always stuck at 0%. The BITS service always crashes immediately on start with code -2147024894 / 0x80070002 I have tried lots of things that worked for other people with this error

• Windows Update troubleshooter tells me it was unable to fix problems
• Renaming C:\Windows\SoftwareDistribution doesn't change anything
• Using regsvr32 on all the DLLs that Windows Update requires doesn't change anything
• sfc /scannow reports that everything is OK
• Running Software Update Readiness Tool does nothing

After too many hours and too many reboots trying to solve this problem, I managed to figure out what it is. I haven't found this solution anywhere else, so I'm sharing here in the hopes that people who have this problem in the future don't need to spend as long as I did fixing it :)

I used Systinternals Process Monitor and filtered on my instance of svchost -k netsvcs. When I attempted to start BITS it gave me 2 registry entries that resulted in NAME NOT FOUND

• HKLM\System\CurrentControlSet\Control\WMI\Security\4a8aaa94-cfc4-46a7-8e4e-17bc45608f0a
• HKLM\System\CurrentControlSet\Control\BackupRestore\FilesNotToBackup

The first one turned out to be useless, but adding a key for the second one fixed the problem! It turns out that BITS was crashing because that key was missing and it needed to write values there.
I can now see BITS entries under that key:

Update: Windows Update still wasn't working even after I got BITS up. Turns out I needed another registry key which was missing, HKCU\Software\Microsoft\Windows\CurrentVersion\Policies\WindowsUpdate