But I've already given an example where it fails hard - "Fedora files" returns very many false hits.

Package Kit is called "Packages", "Software", "Software Install" and "Package Kit". Searching for "Fedora packages" or "Fedora software install" is obviously sub-optimal.

Here's a screenshot for the package kit name thing. Package in the Gnome menu bar, Software in the program's title bar, Software Install and PackageKit in the About dialog.

http://imgur.com/lylItwU

I would prefer the about dialog to contain a magic-word to be used when searching for that software. So, you can call the file manager "Gnome Files", but in the about dialog let people know that "Gnome Files" is "nautilus".

Go is also a pretty good example, you have to search Golang to find results about Go on any engine other than Google's and I would assume I get results on Google, for Go, because I am profiled as a developer. I don't think a lot of thought is put into search brand-ability when it comes to some of these projects, until after the fact.

Programming language names seem particularly bad in that respect: python, ruby, Java, C...

Python is very much googleable, and C isn't that bad either. Just differentiating between C, C++ and C# wasn't possible on Google until lately.

As long as they consistently include the "vendor +" part of the name, then fine... But do they?

[This was a huge annoyance with NextStep-derived projects like gnustep... Because they started from a proprietary system developed in relative isolation, all the apps had super generic names, and culturally they were loathe to make them any less generic. This resulted in a big mess on systems where multiple desktop environments are supposed to live in relative harmony...]