Acho que dpkg -l encontra pacotes mencionados como dependências de pacotes atualmente instalados e não encontra outros pacotes disponíveis. (Aqui “installed” inclui pacotes “conffiles-only”, isto é, pacotes que foram removidos mas não eliminados, listados como uc in dpkg -l .) dpkg -l lista pacotes que são mencionados no arquivo dpkg status ( /var/lib/dpkg/status ).
Pode haver outros motivos que determinam se um pacote está listado por dpkg -l , mas acho que esse é o principal.