I've been having problems with disappearing e-mails also. It has resulted in some serious upset with some of my customers who send me e-mails and expect a reply from me. It happens several times a week. I've tried rebuilding, restarting, and everything else recommended in this thread.
I'm running OS X Mavericks 10.9.5 - the latest update. All of my accounts are POP3. None of them are linked to the same account as they are each for a different company I either own or contract to.
I did finally, after considerable frustration, figure out today what's happening. The e-mails aren't actually lost. They're getting moved to other mail folders where I don't expect to find them. For example, I had a customer e-mail me with some information late yesterday. I replied back to the e-mail advising the customer I would work on the issue this morning. When I went to the mail folder for that customer this morning, the e-mail was gone. I finally found it in the "Sent" folder buried as part of a Conversation. But the conversation belongs in the customer's mail folder and it isn't there. Curiously, if I disable "Conversation Mode" the e-mail disappears from the "Sent" folder and cannot be found in the correct mail folder either. Thus, I know the e-mail is still in my machine but not being properly handled by Apple Mail.
Come on Apple, you can do better than this! It has been a year since the release of Mavericks and you still don't have Mail working to where it is useable, at least in a corporate environment. I'm about ready to dump Apple Mail and use Outlook for Mac.