Vou começar com uma declaração de que isso é baseado no Ubuntu (15.10) e não no Debian, mas eu tentaria adivinhar que ele funcionará da mesma forma. Confirmações, ou correções, se eu estiver errado, são naturalmente muito bem-vindas.
Sua menção ao "estado rc" sugere que você esteja familiarizado com o dpkg . Eu não sei se você tinha algo mais chique em mente, mas por que não usar isso e filtrar a saída para mostrar o que você quer? Por exemplo:
Listar todos os pacotes removidos onde os arquivos de configuração permanecem (a linha começa com rc):
dpkg -l | awk '/^rc/ { print }'
Listar pacotes que não estão atualmente instalados (a linha não inicia com ii):
dpkg -l | awk '!/^ii/ { print }'
O segundo é baseado no pressuposto de que dpkg -l não inclui pacotes que nunca foram instalados, o que pode não ser verdadeiro em todos os casos, talvez especialmente em versões mais antigas.