I've had this problem as well, but I don't perceive it as a rapid change. Rather, I'd say that the quality of Google search has gone down dramatically over the past couple years, and continues to go down. But yes, there have been a couple cases this week that have left me scratching my head. It seems like searches for 'uncommon_word common_words...' now consider 'uncommon_word' to be optional. The case I remember was searching for "chagall russian oven" hoping to find a Marc Chagall painting that I vaguely remembered.
Contrast https://encrypted.google.com/search?q=chagall+russian+oven with https://encrypted.google.com/search?q=%2Bchagall+russian+ove...
I was bothered to find that many of the results, including the top one for Wikipedia, did not include any mention of Chagall. Perhaps even more embarrassingly, several do not even include the word 'oven' but presume that I had misspelled 'over'. I find that I need to use multiple '+' signs in many of my queries to get decent results, seemingly I sometimes even need to use +"quoted phrase" just to find something that includes "quoted phrase". Suggestions of the 'Perhaps you meant' form are great, but automatically switching my query is not a service.
I suppose that Google makes more money with sloppy search than in catering to the likely small number of people who would rather get the results for their exact query than for a best (popular) guess. But it would be nice if there was at least be an expert level configuration option for "Treat all search terms as required".