Enquanto escrevia esta pergunta, ocorreu-me tentar mover a pasta MachineKeys para fora da pasta Restore.
Isso funcionou e eu consegui excluir a pasta.
Ainda tive que excluir cada pasta dentro de Restore manualmente, em vez de excluir a subcamia entre em uma passagem, mas consegui excluí-las.