In my opinion... this thread is missing the context of the words in your titles that have changed. Can you provide more info about the page titles? (Nothing exact, just the types of words, etc)
- Are the pages information or transactional commerce pages?
- Are the first words primarily brand names, or product names?
- Are the middle, or meat of the titles, general descriptive phrases?
I DO understand that you are seeing decay or loss of the leading words in your titles, but without knowing the relevance of those words, the discussion is moot IMHO.
I think the Mayday algo changes were meant to be favorable to brands, so if your titles started with, or had brand names near the beginning as most ecom or transactional pages would, it would actually make sense.