I have been having problems with a couple of Smart Mailboxes not showing all the messages it should - for example one of them is looking at 4 different folders - 2 "On My Mac" and 2 IMAP mailboxes on AOL.com to see if "Message is in Mailbox" and should list the contents of those 4 messages in a single Smart Mailbox.
It gets messages from 3 of those boxes, but not the 4th - an IMAP mailbox from AOL.com. I know the messages are there since I see them when looking at the IMAP mailbox both through Mail, and through Safari.
The other is a trial Smart Mailbox I made that is looking at just the single IMAP mailbox to get the messages in it - this shows no contents at all.
I came across this thread while searching for anwers, and in particular your reply about the length of messages in Console concerning the length of the query string.
For me that error message is 355,797 characters and contains 2,344 occurrences of "!=", so well past your limit of 1,204. The messages in Console seem to be about excluding mailboxes that are in Trash
At the moment SpotLight is rebuilding after I used Onyx to delete the SpotLight Index - I don't know if this will also cure another odd situation I've had for a while - whenever I restart my Mac Pro, SpotLight gets rebuilt which as far as I know is new since I installed Mavericks a few weeks ago.
Roger