dpkg mostrou as informações corretas, os rc sinalizadores em sua saída significando que openjdk-7-jre-headless:i386 foi removido, mas seus arquivos de configuração não foram.
dpkg -l é, na verdade, o front end de dpkg-query -l . Você pode ler o manual do dpkg-query para mais detalhes.