The trouble is, there are three different "versions" of "the search didn't work," only one of which I would say is definitely a bug:

- The thing the user searched for doesn't exist, so it wasn't found. This is not a bug.

- The user did a good job of searching, using relevant keywords etc, but the relevant thing (which exists) didn't come up. This is a bug.

- "Search didn't read my mind" -- if search is a core competency this is a bug, but otherwise I would consider it a deficiency or a missing feature.