Version:            (using KDE 4.0.98)
Installed from:    Gentoo Packages
Compiler:          gcc 4.1.2 
OS:                Linux

When I uninstall a program (ie, unmerge it on Gentoo) and the corresponding .desktop file gets deleted from /usr/share/applications, the Application Launcher Menu (the traditional view, not the new one) starts having several major problems:

1) The application icon doesn't get removed from the menu
2) Most other applications are now un-launchable.  Clicking on their icons does nothing.
3a) If the menu directory is now empty (eg, if I just removed the last entry in "Games"), the directory doesn't get removed, and ...
3b) ... the other directories are now mis-aligned.  Eg, hovering over the "Multimedia" directory shows the contents of the "Office" directory (the one immediately below it).  Hovering over the removed directory (eg, "Games") shows another copy of the root directory.

Re-running kbuildsycoca4 doesn't update the menu.  Only logging out and logging back in fixes these menu problems.