The MS Ribbon comes to mind. It still don't think it's notably better than the original toolbar. But the problem is that shuffling everything around confused many for roughly a year as they had to re-learn where everything is.
MS traded one randomness for a different randomness. Maybe they were thinking a 5% to 10% improvement is worth it over the long run even if they piss off existing customers during the learning curve. So, either they are idiots, or they actually sat around and did "piss off accounting": intentional jerks who willingly sock existing customers in exchange for future news ones. So we have the idiots theory and the jerks theory.
Another thing, redundancy is not necessarily bad in UI's. Some get caught up in the "keep the tree clean" mantra. However, having more than one way to do or find an option often improves the UI. Perhaps an ideally designed UI could avoid the need for repetition, but most designers are not good (or constrained by other factors) such that they should indeed fall back on some redundancy. Rules for ideal conditions (such as great UI) often don't apply to typical conditions (average UI).
For bigger applications, perhaps put all the options in a table(s) and let the users search for options Google-style. That may be faster than digging around in menu trees. You still have menu trees, but ultimately they are tied to the table. Use synonyms and allow bookmarks to improve look-ups. I'd like to see more experiments in Table Oriented Programming. To me, that looks the future. OOP can't handle complex relationships well.