Se um aplicativo estiver (ainda) na lista de aplicativos, isso significa que ainda há um arquivo .desktop representativo do aplicativo em:
/usr/share/applications
ou
~/.local/share/applications
O arquivo "órfão" .desktop deve ser removido, para remover o aplicativo da lista de aplicativos (ou do Dash, se você usar o Unity)
Eu suspeito que é o último mencionado, já que você menciona vinho, e o vinho às vezes instala (muitos) arquivos .desktop localmente. Normalmente, quando você desinstala um aplicativo (não aplicativos wine), os arquivos .desktop correspondentes em /usr/share/applications
são removidos automaticamente.
Encontrando o arquivo .desktop correto
Às vezes, pode ser um pouco difícil identificar o arquivo de área de trabalho correto, pois o nome do arquivo não corresponde necessariamente ao nome do aplicativo. Ao tornar o arquivo de área de trabalho (local) executável, deve ser mais fácil identificá-lo, já que o nome exibido é então igual ao nome do aplicativo, e o arquivo também mostra o ícone do aplicativo, .