The file format "mbox", used to store multiple Internet mail messages in a single file, has problems. Here's what wrong.
The only solution is to stop using mbox, and store mail some other way.
On Unix systems, the most popular other way is maildir. Maildir was designed specifically to be a Unix user's incoming spool and inbox, and it does that well. It can also reasonably be used to store sets of messages for other purposes. Here's Wikipedia's description of maildir.
Unix also has the format used by the mail reader MH. That format is less complex than maildir, and does less -- it doesn't do incoming spooling or concurrent access. It also stores only a limited set of message attributes as metadata. It works well for some uses that don't need all of maildir's function.
Here is dotmail, a new way to store mail on any system, that's equivalent to mbox, but works better.
Here is a summary of some mail storage types, their characteristics, and their uses.