К сожалению запускаться и работать программа-собака отказалась. Удалить тоже не вышло.
Вообще, wine раздражает своим присутствием в меню "Открыть с помощью", конечно, кроме .exe файлов. После установки он пытается открывать jpg, png, gif, html, xml, rft, txt, ini и даже swf. Объявляю ему войну.
Недолго думая, я уничтожил весь каталог с настройками wine rm ~/.wine/, наивно полагая, что решу проблему одним махом. Но не тут-то было.
В /usr/share/applications упоминаний не было найдено, а значит настройки хранятся в домашнем каталоге пользователя.
Смело удаляем лишние файлы и каталоги в .local/share/applications и наслаждаемся чистыми меню в xfce.