Simple, you were so close

it's just not with an exclamation mark:
not in:inbox is the same as
-in:inbox
See this article where I've gathered all the possibilities:
Search Tips - ZimbraWiki
If you think that ! should be added as a common 'exclude' value go ahead and open an RFE in
bugzilla
(and of course if you do be sure to post a link back here so that others searching in the future know)