Incremental feature search the next UI paradigm shift?

Microsoft's new Ribbon interface introduced in Office 2007 is a UI design innovation which may become standard for windows applications, as many companies have already implemented it and Microsoft is even licensing it with MS-enforced guide-lines for consistency.  Although ribbons are intended to make it easier to find commands than the traditional file menu approach, some have suggested that it is still difficult to find featurers when not on the ribbon or when the ribbon becomes too large. As a result, Microsoft has been looking into adding incremental feature search.  Jeff Atwood suggested that incremental feature search could also be a good idea for general application development:

I'm a big fan of incremental search. But incremental search isn't just for navigating large text documents. As applications get larger and more complicated, incremental search is also useful for navigating the sea of features that modern applications offer.

Jeff looks at the Ribbon control introduced in Microsoft Office 2007 and suggests that an incremental search feature would be solution to the problem of not being able to find a command, if the command is not installed in the ribbon. In fact, Microsoft created an add-in called "Scout" that provides this functionality, but have decided not to release it and at this time it is unknown if it will even be available as a separate plugin.

Jeff concludes by suggesting that it is quicker and more convenient to use incremental search over menus and toolbars:

If the evolution of the web has taught us anything, it's that search inevitably becomes the dominant navigation metaphor . Simple applications may be able to get away with menus and toolbars, or better yet, a ribbon. But as the application grows larger and more complex, it's faster to incrementally search for the feature we need.

While incremental search has been used extensively in the past by programs such as emacs, the feature has started to appear in the broader context of operating systems and websites.  For example, QuickSilver is often touted as the quintessential tool for OS X. Vista has jumped on board with the Instant Search feature. Apple recently revamped its website and now features incremental search that filters content from the site, listing shortcuts grouped by areas of the website - products, the apple store, support etc. In the follow up comments to Jeff's blog entry, Christoffer Lernö notes:

After the redesign of Apple's website, it is now MUCH faster and convenient to use search than to actually navigate to the subpage you want.

Are we experiencing a paradigm shift in application navigation? Are the days of traversing a maze of menus and remembering convoluted keyboard shortcuts numbered? What are your thoughts?