I'm testing the fix using two Python processes running mailbox.py, and my test case fails even with your patch.  This is due to another bug, even in the patched version.  

mbox has a dictionary attribute, _toc, mapping message keys to positions in the file.  flush() writes out all the messages in self._toc and constructs a new _toc with the new file offsets.  It doesn't re-read the file to see if new messages were added by another process.

One fix that seems to work: instead of doing 'self._toc = new_toc' after flush() has done its work, do self._toc = None.  The ToC will be regenerated the next time _lookup() is called, causing a re-read of all the contents of the mbox.  Inefficient, but I see no way around the necessity for doing this.

It's not clear to me that my suggested fix is enough, though.  Process #1 opens a mailbox, reads the ToC, and the process does something else for 5 minutes.  In the meantime, process #2 adds a file to the mbox.  Process #1 then adds a message to the mbox and writes it out; it never notices process #2's change.

Maybe the _toc has to be regenerated every time you call lock(), because at this point you know there will be no further updates to the mbox by any other process.  Any unlocked usage of _toc should also really be regenerating _toc every time, because you never know if another process has added a message... but that would be really inefficient.