A lot of poking around and experimentation has brought me to at least a partial understanding of how the dom0 menus function.
I use KDE but I suspect a lot of what I have to say also applies to the default XFCE menu as well.
When a VM (call it my-vm for purposes of this example) is created qvm-appmenus --init and --create is run on it. What gets created as a result of this is:
In $HOME/.local/share/applications, a separate file for each item that that qube has decided should be in the menu (via qvm-features menu-items). This is a desktop file suitable for use on dom0 and this ultimately will be what establishes nodes in the menu.
But also:
in $HOME/.config/menus/applications-merged a single file is created for that vm, named user-qubes-vm-directory-my-vm.menu. If you open that up, it's a list of all of the files in $HOME/.local/share/applications that have to do with that qube.
When you edit your KDE menu to re-organize the listings for qubes, it's basically reorganizing references to this latter file, in this case representing the my-vm node in the KDE menu (wherever it might be based on how you organized it). The organization is described in $HOME/.config/menus/applications-kmenuedit.menu...though as time goes on this file collects a lot of cruft, for reasons I'll get into shortly.
If for some reason you suspect these files are corrupted (as will happen if you do a reset in the KDE menu editor), you can regenerate them with qvm-appmenus --force --update my-vm. (Apparently --force --create is insufficient for this.)
That just leaves one thing and that's the qvm-appmenus --delete command (which is run when you delete the vm). This will of course wipe out the files in $HOME/.local/share/applications that pertain to the qube named in the command, because those commands no longer exist. What it does not do (and IMHO should) is delete the one fine in $HOME/.config/menus/applications-merged subdirectory that pertains to the VM that got removed.
As a result the next time you open the applications editor in KDE to edit the applications, you will see a "ghost" folder in the menu tree, for the removed VM. The menu itself is smart enough to realize there's nothing inside this folder and won't display it, but meanwhile you have this "ghost" folder cluttering up your KDE menu edit application. (And if you delete it, it becomes a branch marked "deleted" in the config file that gets written by this app; part of the cruft I mentioned earlier.) This would be unnecessary if only qvm-appmenus --remove would remove the file for the qube in applications-merged.
I hope this was helpful to someone (though I suspect it's a bit too disorganized to really be of use).