Thanks all for the replies.
Satcomer, I didn't use migration assistant, so no, I didn't "bring over" my mail in that way. I set up my accounts afresh and had my mail populate the new setup.
Namara, I don't have icloud activated for Mail, because at the moment I don't have a need for it. I read Satcomer's link to Apple's info page on smart mailboxes, and it's a simple rundown of the functions. Nothing about icloud/non-icloud.
Taz, I have tried various resyncs and prefs dumps and rebuilds, to no avail.
Still stumped. Very frustrating, because smart mailboxes have been a key part of my Mail use on previous OS's and machines.