Si te estás refiriendo al menú de Aplicaciones en el escritorio, eso se guarda en un archivo de configuración en tu home. No sé cómo es en GNOME, pero por ahí seguro que encontrás el directorio wine con los accesos directos a las aplicaciones que hayas instalado. A lo mejor al desinstalarlo no borra esos archivos.