It's actually not that hard if you know how to make .desktop files and .directory files. I'll try and rustle up a howto sort of thing and post it here.

The whole menu of KDE is the one thing I feel really lets it down

The KDE Menu Editor messed up my menu so bad that I had to learn how to fix it manually. Whenever I need/want to make changes to the menu I do it manually now as I have no faith in the menu editor. Shame really, as I do believe this is one area that Windows really wins one over on KDE/Gnome.

I know this doesn't help anyone much, but just thought I'd add my experience

Cheers,
Dave

Sorry I've been taking so long to write this howto... I've been very busy. I'm planning to submit this as a LinuxAnswer. I'm almost done now but i need a bit of info on other distros. I've got SuSE 9.1 and KDE 3.3.
My files are in:
Main XML file (.menu file) detailing menu structure is /etc/xdg/menus/applications.menu

Menu directories (.directory files) are stored in /usr/share/desktop-directories/
Menu entries (.desktop files) are stored in many places.
Gnome applications: /opt/gnome/share/applications
KDE applications: /opt/kde3/share/applications/kde
Other Applications: /usr/share/applications

User-specfic applications (.desktop files) are in ~/.local/share/applications
User-specific menu edits (.menu file) are in ~/.config/menus/

If ANY of these are different in your installation/distro/version please tell me now!

Ok,
In Fedora Core 2 with Kde 3.2.3-0.1 Red Hat:
All the same, except:
KDE applications: /opt/kde3/share/applications/kde →→→ /usr/share/applications/kde (many *.desktop files)
/usr/include/kde (full of *.h files)
Also, i found a similar thread in another forum,
http://www.linuxdeveloper.net/forum/...ad.php?t=18975
Good luck with the howto.