As pointed out by @radouxju the search for symbols functionality was introduced at ArcGIS 10.0 and from a blog enitled Symbols and styles in ArcGIS 10.0:
Finding appropriate symbols to apply to your features and graphics is
easy in ArcGIS 10 because you can search for and use symbols without
having to know to which style they belong, nor have that style
referenced. When searching for symbols, you can search within all
styles available on your system—including your custom styles—or you
can limit search results to only those styles currently referenced.
Symbols in ArcGIS 10 have searchable tags that describe graphic
characteristics, such color or type. These tags can be modified for
symbols in custom styles to describe any relevant characteristic, such
as a related project, map, layer, scale, or specification.
It sounds to me like the type of search you are looking for is available for custom styles - you just need to add the tags you want to search for - but not for styles that come with ArcGIS Desktop which you can only search for using graphic characteristics.