O gvim aparece se você clicar em Todos os aplicativos?
Se não, eu acho que não há atalho para ele na tela inicial. A razão pela qual ele corresponde ao digitar o nome completo é porque o arquivo .exe está em uma pasta referenciada pela sua variável PATH. O mesmo acontece com certos utilitários do Windows (por exemplo, msinfo32, mmc).