I'm using the fairly old version 9.3 of Mail.app on a computer running El Capitan; I just set up my Gmail account with it, and it seems to be correctly syncing.
For organization purposes, I would love to have a smart mailbox that simply contains every message not in another specific mailbox (edit: that is, a folder), which I'll call A. The problem is that I don't keep any messages directly in A -- I keep them in A's sub-mailboxes (sub-folders) B, C, etc, and the sub-sub-mailboxes of those in turn. So the smart mailbox is not very useful.
Is there any way I can make my dream a reality: A mailbox that only lists messages that are not inside Mailbox A at any level?