Для того, чтоб не сильно париться с установкой и удалением всяких прог под вайном я в какой-то момент делал так:
1. Ставим PlayOnLinux
2. Для каждой проги заводим свой префикс.
3. Прога больше не нужна - просто сносим префикс к чертям.
Получается дешёво и сердито. Плюс имеем доступ ко множеству настроек (правда всё это сомнительной удобности) через правку кой-каких файликов.
А по теме:
если у тебя в программах есть пункт wine->Программы, то должна быть и папочка ~/.local/share/applications/wine/Программы. Убедись, что ты роешься в домашнем каталоге того пользователя. Реестр вайна храниться в ~/.wine/ - правится обычным gedit'ом. Т.е. в общем случае если хочешь полностью удалить программу из вайна, то удаляешь папку с ней из ~/.wine/drive_c, потом настройки например из C:\Windows\profiles\<user>\Application Data и записи в реестре вайна. Ну и настройки всякие не только в AppData могут быть...