The freedesktop.org menu system maintained through Alacarte can be quite a handful if you want it to behave. And then I'm not even mentioning how certain developers screwed their users over with the current implementation in Gnome3, totally ignoring certain parts of the standard because that's the way they want it to be (who cares about following official specifications anyway...).
In the menu system nothing is ever really deleted - it just gets marked as deleted (there's a reason for this which actually makes sense, but I won't go into that now). If you want to get rid of annoying left overs, you have to manually remove the corresponding .desktop files from /usr/share/applications or ~/.local/share/applications or one of their subdirectories.
I don't know about PlayOnLinux, but Wine installs its .desktop files only in the user's directory (i.e. a subdirectory of ~/.local/share/applications). The last time I installed Wine, they ended up in ~/.local/share/applications/wine. Removing that entire subdirectory should do the trick. You may also want to remove any files with names starting with wine- from ~/.config/menus/applications-merged and ~/.local/share/desktop-directories.
Be careful not to remove too much! It's very easy to mess up your entire menu by deleting the wrong thing or making a mistake while manually editing the main menu files in ~/.config/menus.
Edit: another word of caution. My suggestion is based on the normal implementation of the menu standard that the Gnome desktop used to have. I have no idea how much Cinnemon deviates from that.
Edit 2: corrected typos.
Last edited by grizzler
on Thu Mar 15, 2012 1:18 pm, edited 1 time in total.