Como afirmado na pergunta, eu reiniciei o SQL Server sem sucesso.
Eu abri um caso com suporte ao MS e o analista recomendou a reinicialização do servidor SQL e do servidor SCCM.
Eu tentei isso e o servidor agora está sincronizando corretamente com o Windows Update.
A causa original do problema foi que o servidor SQL ficou sem espaço. Eu não tinha essa informação antes. O problema de espaço foi corrigido e o servidor reinicializado, no entanto, uma reinicialização de ambos os servidores foi necessária neste caso.