I just want to add my voice to the chorus as I, too, have been bitten by this bug since installing iOS 9 (actually 9.0.1, then 9.0.2) on my 128 Gb iPhone 6s. The summary posted by Wil616 (I believe it is) mirrors what I am seeing with my Earthlink POP email account (which has been our family's main one for many years). It clearly looks as if POP3 and IMAP are being treated the same way by iOS 9, and to me the loss, after a few hours, of the content of email originating on my iPhone is the most damning.
I have submitted feedback and I've spent a couple of hours on chat with an Apple Support person and the next day about an hour on the phone with another (I do have a case number, therefore). I also described and illustrated the problem to three employees at the Southcenter Apple Store (Tukwila, Washington, near Seattle) when I was in on my birthday looking at (and ultimately purchasing) an Apple Watch.
I've set all my devices to not delete emails from Earthlink's server any more (workaround one). That does NOT solve the loss-of-sent-mail-content issue. I just checked three I sent my son yesterday. They all now show the dreaded "message has not been downloaded...." message. They all had, as part of the original body, an attachment. That seems to also be a factor in this. (Others may have pointed this out but I admit I only skimmed this now 22 page thread before posting.)
I have never been so angry at Apple (yet I bought the Watch anyway). And I may eventually migrate to IMAP even on Earthlink (they now offer it). But there's no excuse for data that originates on my phone, which has PLENTY of storage space available, to be deleted without my permission.
The Watch is complicating some other things, but that is for another thread or two here.....