Estávamos experimentando exatamente o problema que você descreveu.
Recentemente, migramos para o uso de SSDs e, como parte disso, desativamos a configuração "Permitir que arquivos nesta unidade tivessem conteúdo indexado além das propriedades do arquivo" na unidade C.
Depois de reativar essa configuração, descobrimos que as configurações do Painel de Controle retornaram nos resultados da pesquisa (em Everywhere e nas Configurações).