After reflection, I don't think the potential changing actually makes things any worse.  _generate() always starts numbering keys with 1, so if a message's key changes because of lock()'s, re-reading, that means someone else has already modified the mailbox.  Without the ToC clearing, you're already fated to have a corrupted mailbox because the new mailbox will be written using outdated file offsets.  With the ToC clearing, you delete the wrong message.  Neither outcome is good, but data is lost either way.  

The new behaviour is maybe a little bit better in that you're losing a single message but still generating a well-formed mailbox, and not a randomly jumbled mailbox.

I suggest applying the patch to clear self._toc, and noting in the documentation that keys might possibly change after doing a lock().