Huh, it seems to be related to searching two different fields then. In my case I was searching for an author name (though not by tag in that case)
This search will reproduce it in your demo server:
Code:
Conrad and not Tags:=Classics
Should give 0 results, gives 1 instead.
To answer your other question, both 'Tags:=Nopub' and 'not Tags:=Nopub' yield the expected results by themselves.