I'm in here to raise some attention and hopefully some votes for bug 444. The bug was opened in 2005 and requests the implementation of a new search criteria for determining if a mail is tagged or not. The backend work was done fairly quickly and the only thing needed was to add the keyword to the user interface. At least that was then, probably the backend has changed since.
I find it very strange that the function was not finished back in the day but hopefully it can be finished now. It is an important function for me as I want to tag all my incoming and outgoing mail. In Outlook at work I have a routine to open a saved view with only untagged (uncategorized) mail and go through and tagging them. I do this every now and then to make sure I haven't missed tagging anything.
The last comment I got in a forum thread from Zimbra was that the bug is probably low priority due to the low number of votes. I'm hoping this message will change that!