Fixing Smart Mailboxes

I recently had to restore my ~/Library/Mail folder from a Time Machine backup, and upon opening Mail it imported the mailboxes seemingly successfully, however my Smart Mailboxes no longer function, despite appearing to be correct.

My smart mailboxes aren't anything fancy, they basically just group similar items; for example, if accounts A and B both have an IMAP folder named "Newsletters" then the corresponding smart mailbox simply combines messages that reside in either folder; it's a simple match any rule for each mailbox.

However, even though these smart mailboxes appear to be valid (pointing to the correct mailboxes), nothing is appearing within them at all. I've already tried rebuilding every mailbox, as well as closing Mail, clearing its entry under ~/Library/Containers (to force it to rebuild its cache) and relaunching. I've also tried creating new smart mailboxes, but these don't work either, so there must be an index somewhere that's not functioning correctly, but I've already tried deleting the envelope index files under ~/Library/Mail/V2/MailData.

Is there anything else I can do to solve this problem?