Если у вас установлен aptitude, он предоставляет множество шаблонов , которые можно использовать для поиска.
В частности, для случая поиска пакетов, которые предоставляют данный виртуальный пакетимя, вы можете использовать это:
$ aptitude search '?provides(pattern)'
где шаблон может быть установлен на имя виртуального пакета, который вы ищете.
Например:
$ aptitude search -F %p '?provides(mail-reader)'
balsa
bsd-mailx
claws-mail
cone
emacs
emacs23
emacs23-lucid
emacs23-nox
evolution
gnus
im
jed
kmail
kmail-mobile
mailutils
mailutils-mh
mew
mew-beta
mew-beta-bin
mew-bin
mutt
nmh
opera
opera-next
seamonkey-mailnews
sylpheed
thunderbird
tkrat
vm
wl
wl-beta
xemacs21-mule
xemacs21-mule-canna-wnn
xemacs21-nomule
xjed
xul-ext-lightning