Eu me deparei com um problema semelhante. Eu clicaria no botão "Remover" no centro de software, mas os aplicativos voltariam a aparecer após um curto período. Eu fiz isso para o programa Aisle Riot Solitaire, por exemplo, e ele continuou voltando. Quando fui removê-lo com a linha de comando, no entanto, ele disse que não foi instalado:
$ sudo apt-get purge aisleriot
Reading package lists... Done
Building dependency tree
Reading state information... Done
Package 'aisleriot' is not installed, so not removed
0 upgraded, 0 newly installed, 0 to remove and 87 not upgraded.
Após mais investigação (leia-se: clique cego), descobri que clicar no ícone de atualização na guia Atualizações parecia atualizar a guia Instalado também (embora o ícone de atualização não esteja disponível na guia Instalado). Depois disso, Solitaire parou de aparecer.
Por "ícone de atualização", refiro-me à seta circular no canto superior esquerdo.