With Mayflower search, there was the possibility to search for a term and exclude all files in a category. This helped when categorizing images at Commons.
"Tree -Category:Trees" http://toolserver.org/~tangotango/mayflower/search.php?q=Tree&ic=&ec=Trees&ft=any&sc=gt&sv=&ds=&t=n&z=12&a=3 (broken)
It would be nice if this was possible with the standard search at Commons (possibly with Lucene).
*Mayflower search hasn't been updated and is broken for some time.
*A current workaround is to compare the list of results from search with the list from categories.
*[[Bugzilla:21317]] might be related to this.