Smart Mailbox filter "Message is not in mailbox" for iCloud mailboxes
I had the same problem and I found a solution here luckily after searching like crazy. The problem was, that I used my Gmail account as my Apple ID, so mail got confused. After I deactivated mail in my iCloud account settings, it was working fine. This is obviously only a solution if you don't use both accounts. Anyway, maybe it helps someone:


  And here's the solution, or rather the explanation for the problem: If
  you're using your gmail Adress as your apple-id (and therefore as your
  login credentials for your iCloud account) Apple Mail seems to get
  confused. Simply change your iCloud Username to something else and
  your good to go.