I recently saw a problem where a new user installed Wine (a Windows compatability layer) so he could run iTunes. If you want to do it, too, you can foolow the directions for iTunes on Ubuntu just to spite Vista. In the end, though, he didn't have working sound and didn't want to take up space on his hard drive.
Removing iTunes via the uninstaller didn't work for him, either, and removing the Wine application didn't clean up his menu. He was understandably frustrated, and thought his only choice was to go in and manually remove system files. Here's my advice to him (or you, if you're in this position).
Before you delete files manually in the system area (always a bad idea for a new user), go to System -> Administration -> Synaptic Package manager.
Supply your password In the left pane, click to view packages by "Status" and choose the "Not installed (residual config)" section. You'll find Wine in there.
Click on the square next to the wine package and choose "Mark for Complete Removal." This will remove all the configuration files which aren't removed by default (so you don't have to set everything up again if you reinstall). You won't have those system files anymore.
Next, for your menu, open Places -> Home and in the View menu, choose to "Show hidden files." Enter the .config/menus/applications-merged area and delete anything that starts with "wine." Your wine menu entry should be gone now.
This basic procedure will work for any stubborn application which refuses to disappear from your system and your menu.
p.s. Rhythmbox is a good replacement for iTunes and has the bonus of being the default player in Ubuntu. If you don't like RB, I understand Songbird is excellent.