dpkg
pode extrair o nome do pacote (com um pouco de ajuda). O único problema sério aqui é apenas encadeá-los juntos e é aí que find
entra.
find -iname '*.deb' -exec dpkg --info '{}' \; | awk '/Package:/ {print }' | xargs -r -- sudo apt-get remove
Isso não foi testado, mas deve funcionar.