Проблема кроется в Windows Update Agent, который в большинстве случаев успевает поставиться, но далеко не последней версии, и от двух с половиной сотен обновлений у него начинает ехать крыша.
Решение проблемы удалось найти на Microsoft Answers: необходимо вручную поставить два обновления: KB3050265 и KB3102810.
Установку рекомендуется производить сразу после перезагрузки или с отключенной сетью, иначе wusa повиснет на этапе поиска обновления.
После установки каждого обновления потребуется перезагрузка.
В результате даже на хиленьком Атоме все обновления находятся за 20-30 минут.