再起動後、変なプログラム(あれとか、あれとか、あれ)を立ち上げる前(ログイン直後)に、Windows Updateを実行すると、上手くいった。

原因を追求しても、あまり意味がないので、運用で対応する。

つまり、私の環境では、自動WindowsUpdateは必ず失敗するので、定期的に自分で実施する必要がある、ということになる。