Bem, eu encontrei este script
export PACKAGES=$(dpkg -l | awk '{if ( == "rc") print " "}' | tr -d '\n') [ -n "$PACKAGES" ] && sudo apt-get purge $PACKAGES
em ubuntuforums.org que deve limpar as instalações removidas. Então talvez funcione também para limpar o menu.