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 .