10.9 Mail "smart mailbox" doesn't filter properly

Here are two more possible solutions.

Reset Permissions

chmod -a 'everyone deny write,delete,append,writeattr,writeextattr,chown' ~/Library/Mobile\ Documents/com~apple~mail/Data/MailData/* ~/Library/Mobile\ Documents/com~apple~mail/Data/MailData/Signatures/*

This resets permissions on email related items (you can reset permissions on everything in Disk Utility).

Remove Indexes

rm -rf ~/Library/Mail/V2/MailData/Envelope*
mdimport ~/Library/Mail

This second possibility gets rid of Mail's index (Mail will rebuild it upon restart) and refreshes Spotlight with your email content.