aptitude tem seu próprio banco de dados de estado de pacote /var/lib/aptitude/pkgstates , que infelizmente parece não estar documentado. Ele armazena um bloco como este para cada pacote:
Package: bash
Architecture: amd64
Unseen: no
State: 1
Dselect-State: 1
Remove-Reason: 0
Eu acredito que o estado 1 significa installed , o estado branco 3 significa not installed . Eu também tenho alguns pacotes com o estado 4 no meu sistema, mas não consigo descobrir o que isso significa.
Acredito que o seu problema seja resultado da inconsistência entre o dpkg database /var/lib/dpkg/status e o aptitude database /var/lib/aptitude/pkgstates . De acordo com este post pkgstates deve refletir "o estado pretendido pelo usuário" para o pacote [s] ", então o aptitude provavelmente acredita que o usuário deseja que esses pacotes sejam instalados mesmo que o apt-get tenha acabado de removê-los.
Parece que a melhor solução para o seu problema é fazer o que o tripleee sugere: use aptitude se ele estiver instalado e, caso contrário, volte para apt-get .