In many ways the world is going towards more incremental/predictive searching: Google incremental/predictive search, FireFox Awesome bar, Win7 Start Menu search box, ... If it's done right it's a powerful interface feature.
That's true, though in some instances it's going against a local cache and not a data store. And perhaps I'm in the minority, but I sometimes find those features annoying.