Три года назад решал аналогичный квест с Wine (тогда еще под Fedora жил). После удаления штатными средствами yum (с зависимостями) обнаружил тем же образом -- Wine продолжал открывать файлы в браузере каким-то своим viewer'ом.

Сделал rm ~/.local/share/applications/wine* и всё, что нашлось по find / -name wine. Но самое интересное, что через месяц после этого всё равно увидел в обнволениях wine-core и wine-filesystem, доудалил их тоже. После этого вроде Wine'овых следов в системе не замечал, но зарёкся эту дрянь никогда больше даже палкой не тыкать.