I have found a solution.
The basic idea is that the *.desktop file in .local/share/applications needs to be identical to the one in /usr/share/applications/
This is the one I use for Palemoon:
[Desktop Entry]
Version=1.0
Comment=Internet Browser
Terminal=false
Name=palemoon
Exec=/home/$USER/.palemoon/palemoon
Type=Application
Icon=/home/$USER/.palemoon/browser/chrome/icons/default/default48.png
StartupWMClass="Pale moon"
Categories=Application;Network;WebBrowser;
MimeType=text/html;text/xml;application/xhtml+xml;application/vnd.mozilla.xul+xml;text/mml;x-scheme-handler/http;x-scheme-handler/https;
StartupNotify=true
Actions=new-window;new-private-window;new-tab;
[Desktop Action new-window]
Name=Open a New Window
Exec=/home/$USER/.palemoon/palemoon --new-window %u
[Desktop Action new-private-window]
Name=Open a New Private Window
Exec=/home/$USER/.palemoon/palemoon --private-window %u
[Desktop Action new-tab]
Name=Open a New Tab
Exec=/home/$USER/.palemoon/palemoon --new-tab about:newtab