Sometimes we fetch results for queries that are related to the original query but have fewer words. We made several changes to our algorithms to make them more conservative and less likely to introduce results without query words.
Although that description doesn't match your exact situation, it does make me wonder what exactly they were tinkering with and if it might have implications that do affect your results.
Then again, I've often seen weird search results for relatively new pages that seem to stabilize after a bit more time. Have you tried the intitle: search operator?