Da resposta a esta pergunta: Como desinstalar todos mas os pacotes padrão do Ubuntu? :
comm -3 <(cat filesystem.manifest | awk '{print }' | sort) <(cat filesystem.manifest-remove | sort) > default.txt
dpkg --get-selections | awk '{print }' | sort > current.txt
diff -u default.txt current.txt | grep "^+[^+]" | cut -c 2- > installed.txt
diff -u default.txt current.txt | grep "^-[^-]" | cut -c 2- > uninstalled.txt
Isso faz 4 arquivos: default.txt é a lista de todos os pacotes padrão, current.txt é a lista de todos os pacotes atuais, installed.txt é a lista de todos os pacotes que você adicionou, installed.txt é o que você quer ver, tem todos os pacotes que você removeu.
Você pode fazer cat uninstalled.txt | grep wine
para listar todos os pacotes desinstalados relacionados ao vinho.
Supostamente, isso poderia instalar todos os pacotes que você removeu, mas eu não contaria com isso:
sudo apt-get install ubuntu-desktop