OK, I have a prototype implementation, and I want to sanity check it before I go on. I will do this with a set of screen captures.
The first shows grouping by tags/first letter.
The second shows the result of a long press on "S". This is the dialog that you see, giving you the choice of finding all books that match the item or all books that do not match the item.
I tapped the "Matching" button, which says find books with a tag beginning with "S". The books have other tags, so those tags are shown as well. The header shows the calibre- and CC-equivalent search.
If I wanted to I could change the grouping to by Series, by Author, or by anything. I could even turn off grouping. I would see only the books that have a tag beginning with S. This behavior is like calibre's restriction, in case you have ever used that. @Dopedangel: this is how you would view authors of books tagged with "Fantasy". You would long tap on Fantasy, select "Matching" to get the books with that tag, then group by Authors.
The next screen shows what happens if I tap "Not matching", which finds all books without a tag beginning with "S". The header now has a "not" in the search string to tell you what it is doing. Note that there are no longer any "S" tags in the list, which is good because we asked for books with no tags beginning with "S".
For the next screen, I cleared the search and then tapped on the tag "S" to open the list of tags beginning with S. I see three tags, one of which is not related to science fiction.
I then long tapped on "Space Opera" and chose "Match", which selected all books with that tag. All my books with the tag "Space Opera" also have the tag "Science Fiction".
The last screen shows what I see if I chose "Not match". I see all the books that do not have the tag "Space Opera". Note that the list of books with the Science Fiction tag is different from the screen shot above, because it is now showing books with "Science Fiction" but without "Space Opera". The non-fiction tag also appeared.
Does this make sense to people? I know that it is hard to really know what something does without being able to play with it, but it would be a shame if I got this wrong coming out of the gate.