This one was buggin me for a long time as well, at least ten times a day since Mountain Lion. So putting on my developer hat, looked at messages in Console and observed this:
08/11/2012 23:01:35.172 Mail[312]: Failed execution of AppleScript: /Users/<uc>/Library/Application Scripts/com.apple.mail/Remove Messages From Sender or Thread.scpt
Error Domain=NSPOSIXErrorDomain Code=2 "The operation couldn’t be completed. /Users/<uc>/Library/Application Scripts/com.apple.mail/Remove Messages From Sender or Thread.scpt: execution error: Mail got an error: User canceled. (-128)
" UserInfo=0x7f9fb233c6b0 {NSURL=file://localhost/Users/<uc>/Library/Application%20Scripts/com.apple.mail /Remove%20Messages%20From%20Sender%20or%20Thread.scpt, NSLocalizedFailureReason=/Users/<uc>/Library/Application Scripts/com.apple.mail/Remove Messages From Sender or Thread.scpt: execution error: Mail got an error: User canceled. (-128)
}
Solution: remove this kill script from Library/Application Scripts/com.apple.mail/Remove Messages From Sender or Thread.scpt
That seems to be the cause of the problems. I have now run 24 hours without a repeat message.
Mailbox > Rebuild did nothing expect reload megabytes (around 12,000) messages from the servers.