On Qubes xfce 3.2 I had the entries in ~/.local/share/applications
and the directories in ~/.local/share/desktop-directories
not sure if it is the right place to clean up however...
It worked for me.
Got rid of the old fedora-23 and debian-8 listings by doing as suggested above. ie. going to ~/.local/share/applications and doing rm -fr <each entry for the vm to be removed>
Once each listing for,eg. fedora-23 was removed then fedora-23 disappeared from the drop-down.
Could probably have done it quicker via ~/.local/share/desktop-directories though?
Thanks for the advice @Tom Zander and @dy...@riseup.net