Can I prevent OS X 10.8 Mail.app smart mailbox configuration changes/corruption?
The problem indeed was with synchronisation: my iMac had this account configured as name@company.com, while MBA had this account configure as name.alias@company.com. Once I have deleted all IMAP accounts from both iMac and MBA and created it once again, problem disappeared.