I found a solution that apparently works, at least for my two computers: Boot from an external USB (or CD) with a different OS (any live Linux distro or Windows utility app should work), and from there delete all content of the folder C:\Windows\SoftwareDistribution. After rebooting, take care of whatever is left your trash can. Run again the clean-up app and those extra gigabytes are gone. Windows Update shows only the typical residual small files but no more gigantic Updates. Everything seems to work fine and new updates will keep coming when available. As soon as they become huge again, repeat the process and you are done.
Another way to do this from "inside" Windows (in a running Windows), instead of "outside", is to stop the services Windows Update and Background Intelligent Transfer Service (BITS) before deleting the C:\Windows\SoftwareDistribution folder, and then start them again.