Question about mailbox-update-doc: the add() method still returns self._next_key - 1; should this be 
self._next_user_key - 1?  The keys in _user_toc are the ones returned to external users of the mailbox, right?

(A good test case would be to initialize _next_key to 0 and _next_user_key to a different value like 123456.)

I'm still staring at the patch, trying to convince myself that it will help -- haven't spotted any problems, but this bug is making me nervous...