You think your menus are a mess ? You should see mine....
I really wish KDE would at least (optionally) put them in alphabetical order automatically, if told to do so. GNOME, XFCE4, and E17 do so. Instead, KDE just piles new ones at the top of the menu list(s). At least, it does so on this machine. Launchers for erased packages often remain. I think I currently have three launchers for VLC... maybe more.
Anyway, the menu editor is part of the kdebase package, and I know that GNOME has a menu editor too. But barring manual reorganizing via those menu editors, I don't know of any other handy utilites for the task that you seem to have in mind.