Você pode usar o seguinte comando para listar ícones de aplicativos vinculados a programas inexistentes:
for i in {/usr,~/.local}/share/applications/*.desktop; do which $(grep -Poh '(?<=Exec=).*?( |$)' $i) > /dev/null || echo $i; done
Suspeito que você descobrirá que a maioria dos seus ícones são personalizados em sua pasta pessoal, já que eles não são limpos automaticamente pelo gerenciador de pacotes. Se este for o caso e você gostaria de lixo todos de uma vez, você pode usar uma modificação do comando anterior:
for i in ~/.local/share/applications/*.desktop; do which $(grep -Poh '(?<=Exec=).*?( |$)' $i) > /dev/null || trash $i; done
Ou, é claro, navegue até ~/.local/share/applications/
no Nautilus e descarte-os pela interface gráfica.