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

It depends entirely on the commitment made by the service, so e.g. my desktop file search program results has bugs whereas Google's has none.