aptitude pode fazer essa consulta para você, com a pesquisa ~o ("o" para "obsoleto"):
aptitude search ~o
lista os pacotes que não podem mais ser baixados.
Eu não acho que haja um apt-cache search equivalente e não tenho certeza sobre o synaptic.
Para mais informações sobre termos de pesquisa com aptitude , consulte a seção termos de pesquisa no guia de referência do aptitude .