Originally the Zieglers did not want any search capabilities on the site - as they pointed out "...the old BR catalogs didn't have an index so why would the site have search? We want a totally different experience..."
That idea got lost.
We used a combination of Verity and Dynamo/Oracle to provide product search capabilities.
We initially split Search into two metaphors - Category search and Product Characteristic search.
Category search (also called "hierarchical search" in-house) was actually a dynamic 'drill-down' tool with a Verity backend.
Product Characteristic search was the typical "Shirt/Blue/Mens" keyword search.
We dropped the Product Characteristic search pretty quickly, replacing it with a Product ID search.
The Product ID Search allowed return, or 'replenishment' shoppers to quickly find a favorite item. (Recall that the on-line Catalog shots moved around as per the requests of the Merchants/Zieglers.) When we started using print catalogs Product ID Search was labeled 'Catalog Search.'
Verity was loaded by Java/JDBC programs which extracted product information from our Oracle database tables.