I'll start with a disclaimer that this is based on Ubuntu (15.10) and not vanilla Debian, but I would tentatively guess that it will work the same. Confirmations, or corrections if I'm wrong, are of course most welcome.
Your mention of "the rc state" suggests you are familiar with dpkg. I don't know if you had something more fancy in mind, but why not just use that and filter the output to show what you want? For example:
List all removed packages where config files remain (line starts with rc):
dpkg -l | awk '/^rc/ { print }' List packages that are not currently installed (line does not start with ii):
dpkg -l | awk '!/^ii/ { print }' The second one is based on the assumption that dpkg -l does not include packages that have never been installed, which may not hold true in all cases, perhaps especially with older versions.