There's been a lot of discussion about a substitution to current kmenu, but almost all of them have just arranged the menu differently. I don't think this kind of approach is much better, since people have more and more applications. That's why I tried to design a more precise application launcher, which would also be fast and easy to use. I posted some mockups to kde-look, and it has the best rating of all ALI ideas at the moment. You can find it here:
http://www.kde-look.org/content/show.php?content=34997. I hope there would be something like this in KDE4 at least as an option.