Já corri para este problema duas vezes. Quando o Windows inicia a manutenção automática, o computador fica sem resposta e, eventualmente, congela.
E nas duas vezes eu consegui fazer o backtrack do problema para editar o registro. Desfazer as alterações no registro resolveu o problema e a manutenção foi concluída sem nenhum problema.
A primeira vez foi com o CCleaner. Eu corri a limpeza normal, incluindo a limpeza de entradas sugeridas do registro. Depois tive que restaurar os backups do registro e o problema desapareceu.
A segunda vez foi quando eu queria testar alguns softwares muito antigos que não funcionavam mais no Win8. Eu tive que executar o arquivo, incluindo as entradas do registro manualmente. O software estava funcionando, mas depois foi removido por causa do congelamento de manutenção. E novamente desfazendo a edição, o problema de congelamento desapareceu.
Agora a questão é por que e como isso acontece?
Existe algum tipo de backlog para edições de registro, e quando o sistema operacional não consegue descobrir quem / o que a edição congelou? E é possível que o usuário edite o registro sem causar problemas como esse?
EDIT: OS foi originalmente o Windows XP, atualizado para o Windows 7 e, posteriormente, atualizado para o Windows 8 e 8.1