Para responder a minha própria pergunta, descobri como estava funcionando:
Fora da caixa, o campo de pesquisa no menu iniciar tem sua própria configuração para pesquisar apenas nos arquivos do usuário atual. As opções de indexação do Vista não têm nada a ver com isso.
Você pode realmente ajustá-lo para trabalhar com o serviço de indexação de pesquisa do Vista, você terá que clicar com o botão direito do mouse na barra de tarefas e selecionar "Propriedades" - > "Menu Iniciar" - > "Personalizar" e rolar um pouco para encontrar as opções desejadas.
Isso responde à minha pergunta inicial. Eu nunca fiquei satisfeito com a velocidade dessa caixa de pesquisa e ela não parece "aprender" quais programas você inicia com frequência e por isso optei por instalar Launchy , que é muito mais rápido e inteligente.