A razão pela qual não está aparecendo em sua pesquisa parcial é porque ela é considerada uma Ferramenta Administrativa.
Ferramentas administrativas não aparecem por padrão, e é por isso que você precisa digitar o nome completo do executável.
Felizmente, um recente A entrada do blog do MSDN explica isso em detalhes, incluindo instruções sobre como fazer isso aparecer.
Tomando um trecho, funciona assim (formatação adicionada por mim):
You can enable the Administrative Tools on the Start screen by:
Opening the Start screen
Opening the settings for the Start screen with Win+I (Tip: Win+I is a context sensitive hotkey to bring up the settings for the app you are using, even if the “App” you are using is the Windows Desktop)
Selecting the “Tiles” option and toggling on the "Show administrative tools" option.
Tada! I can now search in the Start screen for PowerShell.
Verifiquei que isso funciona na versão RTM do Windows 8.