Thanks to a comment by Siraj Razick I became aware of the development of the future KDE 4 menu: codename “Raptor”.
Ratpor will be a plasmoid, a Plasma widget, and therefore building upon newest KDE 4 technology which takes care of stuff like resizing. Also there will be a clear separation from data sources and presentation – something which is a basic design principle for all KDE 4 widgets to make widget development easier (for more information see one of Aaron Seigos presentations about Plasma).
The main goals of Raptor are clear: to provide a high quality menu everyone will like. This includes an intelligent “My Favourite” section (intelligent means really intelligent and not the stuff available today), a skin supported menu (png or svg, colour, layout), fancy effects (“rain in the menu”, whatever that means) and of course searching of all entries – at the moment implemented with strigi (which was mentioned pretty often at akademy – hope it gets even more boost!).
There are also other ideas listed, however it is not entirely clear how far these have been implemented or just discussed: plugin support (at least for other search machines like beagle instead of strigi), tag support for menu entries, even with weighted tags and other stuff. For more details, look at their project page.