Tanto quanto eu entendo seus requisitos, a opção madison para o apt-cache faz o que você quer:
madison / [pkg (s)]
O comando madison do apt-cache tenta imitar o formato de saída e um subconjunto da funcionalidade da ferramenta de gerenciamento de arquivos Debian, madison. Exibe as versões disponíveis de um pacote em um formato tabular. Ao contrário do madison original, ele só pode exibir informações para a arquitetura para a qual o APT recuperou listas de pacotes (APT :: Architecture).
No meu computador:
$ apt-cache madison f-spot
f-spot | 0.7.2-1~ppa~lucid0 | http://ppa.launchpad.net/f-spot/f-spot-ppa/ubuntu/ lucid/main Packages
f-spot | 0.6.1.5-2ubuntu7 | http://ro.archive.ubuntu.com/ubuntu/ lucid-updates/main Packages
f-spot | 0.6.1.5-2ubuntu6 | http://ro.archive.ubuntu.com/ubuntu/ lucid/main Packages
f-spot | 0.6.1.5-2ubuntu6 | http://ro.archive.ubuntu.com/ubuntu/ lucid/main Sources
f-spot | 0.6.1.5-2ubuntu7 | http://ro.archive.ubuntu.com/ubuntu/ lucid-updates/main Sources
Espero que isso seja o que você precisa. Inclui também o ppas.