Parece algo que a Microsoft supostamente corrigiu no ano passado. Verifique se você tem o Hotfix KB977380 instalado ou não. Se não, você pode querer dar uma chance.
Você também pode tentar a solução Corrigir da Microsoft intitulada Corrigir a pesquisa da área de trabalho do Windows quando ela falhar ou não mostrar resultados e veja se você está obtendo alguns resultados.
Se isso não funcionar, você sempre pode tentar excluir o seguinte arquivo. Parece que pode ser corrompido facilmente.
%localappdata%\Microsoft\Windows33\StructuredQuerySchema.bin