At what point does search quality degrade to the point where is becomes a bug?

A bug is when actual behavior does not match stated or intended behavior. If the search bears little connection to what was searched for, then it is a bug, as far as the user is concerned.

Or maybe you mean to say we should reserve the word bug for deviations that are unintentional?