> Might the perceived quality decrease be based on a misclassification of the user entering the search
Exactly! Search engine performance can be assessed by measuring precision and recall [0]. Full text search engines have really high precision. Additionally, when the user has been socialized with full text searches, they've built a model of how the search engine works ("it will find documents which contain my search phrase"), so false negatives are perceived to be less severe, as they can be readily explained by the model. "Ah, this document about helicopers contains 'Apache', no wonder it's in the results. I'll add 'webserver' to narrow it down" (And experienced users will already start off with all necessary key terms).
While full text search engines have high precision, they also have bad recall. This can be improved, but there is a tradeoff when tuning the algorithm: to increase recall, the search context is broadened. That necessarily decreases precision as well, because there is no way the search engine is always correct when adding context. Also, when at first all documents on the frontpage at least contained the search term, now there is not even a good explanation why some documents were retrieved. And the more precise the query itself (something we learned by using full text searches) the higher the probability of misclassification, and the worse the effects of broadening. The relevant results are somewhere in the list, but now every second result on the frontpage is from the wrong bucket. And with no explanation, those false positives weight heavy for us users from the old days.
[0] Precision is the probability that a random document in the result set is relevant. Recall is the probability that a random relevant document is in the result set.