To prevent duplicate: The detailed description is here:
viewtopic.php?t=50137
Summary:
In the use case MP shows (by icon) it does it, but actually does not.
Additional argument:
A category assigned has the same informational quality as a category not assigned.
So searching for images categorized "elephant" is as appropriate
as searching for images that are not categorized as "elephant".
There is no reason why searching for not-assigned category should be only possible
on a a subset of the images (defined by being assigned with another category).
Practical example:
You want to check if you haven't forget any of your elephant images
being assigned with category "elephant".
This is important, as a missing category on images will "hide" it
(at filter/ search) for ever.