Reading all the posts about the range of problems that appear in Mail under iOS 9.1 (in my case on an iPhone but the same problem), I am struck by the similarity to problems I often saw when I was a programmer. These sort of random symptoms nearly always meant one thing:
The program or app is writing some data to the wrong part of the program's memory.
In my experience, this was usually caused by "Array Out Of Bounds" (see below), but surely the moderns compilers are checking array subscripts (offsets) to stop that particular way of writing to the wrong part of memory these days.
However, It still seems likely to me that the Mail app is writing data to the wrong part of its memory (memory in the App, not physical memory). Something Apple can try and find a fix for, I would have thought.
Elizabeth
* Array out of Bounds works like this: Suppose a program has [an array of] 20 messages in Trash, each addressed using their offset or relative position from the start - numbered 0 to 19. Suppose the code is then written to delete them all by Deleting message [N] where N goes from 1 to 20. Then the last attempt to delete, when N=20, will be a message too far, since the list only goes from 0 to 19. and in trying to delete the data stored immediately after the last message it will delete something else. This might - sometimes - be the contents of a message in INBOX for example!