i created several SmartMailBoxes in Apple Mail.
After reboot they are gone.
~/Library/Mail/V2/MailData rights are correct (644 for owner and grp staff)
And no messages at the console.
System: MBA 2011 with 10.7.3 and an exchange and MobileMe account.
When they disappear, check your MailData Folder and see if the smartmailbox.plist files are still there.
You might also try looking at the Saved Application State folder in your home library. Check the com.apple.mail.savedState folder and see if it's locked. If not, try trashing that folder.