Indeed, there are lots of challenges with faceted search in practice.
With regard to the three problems you raise:
1) I agree that faceted search has a way of unlocking the poverty in the data. Unless you already have robust metadata, you need to invest in some kind of data enrichment and cleansing before you can expect to get much value from faceted search. But, done right, you get a virtuous circle of making investment in the areas of data enrichment that searchers want to use to navigate the corpus.
2) A purist implementation of faceted search may be brittle, but there’s no reason to be so purist. As you said, there’s often a natural distance function you can use to offer useful query relaxations. You can use this to rewrite the query and expose potential relaxations to the user once they’ve selected facet values. Indeed, a faceted model should make it easier to do so. But I agree, this is an editorial, application-level decision — though hopefully it’s data-informed so that the proposed relaxations are ones users will appreciate.
3) I don’t see how incomplete options are an inherent problem with faceted search. It’s easy to implement negation within faceted search, as well as to allow any blend of ANDs and ORs within or even across facets. The challenge tends to be usability. For example, most users are accustomed to OR within facets and AND across facets, so if you’re going to violate that expectation you have to signal it clearly. I use negation all the time as an operator in the search box, but I wonder how often the utility it provides to a faceted search interface justifies the added complexity. As for ranges of facet values, I find those pretty standard in faceted search today — indeed, they ship with Solr. And it’s not hard to have overlapping ranges (e.g., 5 stars, 4+ stars, etc.). Of course, you have to have a total ordering if you’re going to offer ranges.
Anyway, I feel the bigger challenge today is that everyone got used to having enough screen real estate to put facets in the left rail, and that breaks down on mobile devices. I like the pattern of using a horizontal bar at the top of the results, but it requires extremely judicious use of the limited space. What I see happening increasingly is that faceted refinement is moving into the query formulation process, with autocomplete suggestions taking users to searches already refined by facets.
And we’ll have to see what happens with voice search!