echo ls| ftp ftp://server/dir/subdir/ | grep -i package
This is so cool. Mind you, it does not search recursively. Also, the "/" at the end of the path is important. But you can load your repositories into a variable and then search for software anytimefast.(Unless the trick gets too popular and the ftp-servers break).
Note: On Gutsy it seems "ftp" does not do this, use lftp instead.