I have been dealing with this issue for a long time and I finally was able to spend the time necessary to solve it in my case.
The problem, in my case, was with the HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Internet Settings\Connections registry key.
Below are the working and non-working registry keys. You should be able to simply delete the key and reboot and the key values will be recreated with working ones.
If you import the working values, no reboot is required.
Working
[HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Internet Settings\Connections]
"SavedLegacySettings"=hex:46,00,00,00,02,00,00,00,01,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00
"DefaultConnectionSettings"=hex:46,00,00,00,02,00,00,00,01,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00
Not working
[HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Internet Settings\Connections]
"SavedLegacySettings"=hex:46,00,00,00,04,00,00,00,00,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00
"DefaultConnectionSettings"=hex:46,00,00,00,04,00,00,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,\
00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00
Thanks for taking the time to work this out! Tried this for an end user and it worked. I checked the keys on other computers in my organization and modified the keys on the problem computer to match those. And voila, was able to log into Office products.