Claro que há uma pesquisa; -)
Vá para a MS Store - > mova o mouse para o lado direito da tela (menu contextual com configurações deslizar para fora) search é o primeiro item - > tipo smartglass - > é o primeiro link
Não é intuitivo, mas a pesquisa é SEMPRE contextual, ou seja, quando você pesquisa na tela inicial, ele pesquisa em seu computador, quando na loja ele pesquisa aplicativos, quando em música ele procura músicas / MP3
faz sentido?
Screenshot: