On Fedora 14, searching for "video editor" returns a bunch of irrelevant search results, such as alacarte, audacity, CGDB, anjuta, etc.
I'm guessing they are shown because they have the word "editor" in their description.
Yes, gpk does an OR search by default. Some of the PackageKit backends don't yet support doing "AND" searches, although when 0.6.x forks we'll probably switch the default then and force the other backends to catch up.
I still don't think we can do this without client-side filtering. :(
For what it's worth I retested this now and it still affects GPK 3.21.x