Some time ago I wrote a proposal for reorganizing app menu.
I started implementing it a month ago by writing an alternative applications.menu. As it relies on freedesktop.org spec categories specified in .desktop files, and not all applications are good citizens in that regard, my first steps were to bug application developers to add subcategories to their apps' .desktop files. I also walked through KDE apps and updated their desktop files. All the bugs I reported were fixed, except for the OpenOffice.org one.
Of course, I made a screencast of the results.
I prepared a simple script that you can run [as root] to get same results. The package also contains updated .desktop files (it installs desktop files only for apps present in your system), and it backs up the old kde4-applications.menu (yes, in my debian system it has kde4- prefix).
If anyone likes the alternative layout please let me know.