I have a smart mailbox setup to combine the inboxes of my 3 Gmail accounts. It worked great in 10.8. In Mavericks, this "smart inbox" frequently shows messages which have already been archived, and do not appear in the regular Gmail inbox within Mail.app. This screenshot shows an example. So Mail recognizes that the two messages are archived, yet they still show up here. These two messages do no appear in the regular Gmail inbox within Mail.
I have already tried deleting and recreating the smart mailbox. I show its settings below.