Nicht schick aber tut was es soll:
aptitude purge $(dpkg -l | grep -v ^ii | while read line; do echo -n "$(echo $line | awk '/amd64|all/ {print $2}') "; done)
Wir holen uns alle Pakete welche nicht den Status ii haben (installiert), aus dieser Liste nehmen wir alle aus den Architekturen amd64 oder all (entfernt einige Kommentare die mit ausgegeben werden), dann geben wir die Paketnamen der einzelnen Zeilen mit einem Leerzeichen getrennt aus und übergeben das ganze Konstrukt an aptitude.