Tem a certeza de que removeu a aplicação ou apenas o mosaico? Para remover o aplicativo, clique com o botão direito do mouse e escolha Desinstalar. Em seguida, ele deve pedir confirmação, clique em desinstalar novamente e ele deve desaparecer.
Caso contrário, existe o risco de você ter removido o bloco da tela inicial e ainda estar disponível em Todos os programas. Você pode acessar a tela de todos os programas clicando com o botão direito em uma área vazia da tela inicial e pressionando o botão que aparece no canto inferior direito.