Yeah, for something like that, you really need some form of navigable index or sitemap. Used to work for an auto classifieds site, and the sitemap and updating with the latest items daily was key to the google fu. Along with navigable entry points to search results.

Kind of counter intuitive for effectively a search though.