Como quase todos os programas principais do Windows e muitos aplicativos de terceiros usam o registro, se o registro estiver cheio de chaves não usadas, segue-se que o acesso ao registro é mais lento.
Assim sendo, para fazer uma diferença real no desempenho, você provavelmente precisará excluir milhares de chaves. Wil mencionou o CCleaner, e toda vez que eu corri isso, a maioria das chaves que eu vi deletar é de cerca de 400.
Eu diria que as únicas situações em que uma limpeza de registro é realmente garantida é se você está preparando a máquina para ou transferindo para um novo usuário, já que a limpeza do registro exclui muitas listas MRU que possuem itens acessados recentemente.