Alguém poderia me dizer qual é a diferença entre eles?
O que você está vendo é porque dpkg -l
consulta apenas o pacote já instalado (ou removido, mas não eliminado). apt-cache search
procura todos os repositórios independentemente se está instalado ou não, então se você precisa saber se um pacote está disponível você pode usar apt-cache
se você quer saber se um pacote está instalado você pode usar dpkg --list
.