I would opt for removing hp-toolbox.desktop
The hplip package in Debian contains only hplip.desktop file, this is what caused the duplicate menu entry:
1) On merge of hplip 0.9.11-2ubuntu1 hplip.desktop was renamed to hp-toolbox.desktop, hp-fab.desktop and hp-sendfax.desktop were added by Matthias Klose.
2) On merge of hplip 1.7.1-1ubuntu1 you (Till Kampeter) did copy the missing desktop files from the previous ubuntu package, since hplip.desktop is already in the debian package this leaves us with 4 desktop files: hplip.desktop, hp-toolbox.desktop, hp-fab.desktop and hp-sendfax.desktop.
Since Ubuntu uses co-maintainership we should avoid this problem for future merges from Debian, I suggest we keep the original hplip.desktop file name (add NoDisplay=true for people without HP printers) and remove hp-toolbox.desktop, unless we can convince Debian to rename the file.
If I'm correct the idea behind gnome-app-install is to add/remove an application by menu entry (desktop file).
I don't think that the file name of a desktop file needs to match the package name for gnome-app-install, but Michael should confirm this.
Does gnome-app-install ignore NoDisplay=true so users will be able to remove hplip by finding "HPLIP Toolbox" when they don't want it?