Eu mesmo encontrei a resposta com a ajuda da especificação freedesktop.org
Houve um gnome-applications.menu em ~/.config/menus e como a variável env XDG_MENU_PREFIX foi definida como "gnome-" a versão gnome trumped my applications.menu.
Renomear meu applications.menu para gnome-applications.menu resolveu o problema