If you're interested in rediscovery:
On Gentoo you can do something like this to find all binaries in all installed packages
for pkg in `eix -I --only-names`; do echo -e "$pkg : \n"; (equery files $pkg | grep -i 'bin/'); done
It produces something like:
app-accessibility/espeak :
/usr/bin/espeak
app-accessibility/festival :
/usr/bin/audsp
/usr/bin/festival
app-accessibility/flite :
/usr/bin/build_flite
/usr/bin/dump_cst_regexes
/usr/bin/dump_us_regexes
/usr/bin/find_sts
/usr/bin/flite
/usr/bin/flite_sort
/usr/bin/flite_time
/usr/bin/huff_table
/usr/bin/regexcomp
/usr/bin/setup_flite
/usr/bin/t2p
I imagine other package managers have similar ways of doing stuff like that.
You can get pretty creative with these things in order to produce something searchable or generate menu's.