I have the same issue. I have identified at least 4 other separate threads on the apple forums as well as numerous threads on other forums. I will attempt to précis them here and also provide links so you can read through my sources yourselves. Note there is, as always, a significant amount of duff information, guessing and questionable fact obscuring the useful evidence.
1. this issue only appears to be affecting people with email accounts set up for pop/smtp.
2. Following upgrade to iOS 9 / iOS 9.01 and possibly the 9.1 beta as well, email content is removed from the iOS device resulting in a sudden decrease in the storage required for the mail app.
3. Emails that may have been present on the device for many months and accessed multiple times in both the inbox and sent items will be randomly replaced with the basic placeholder information (similar to a IMAP case prior to download) but the body will be replaced with the statement: This message has not been downloaded from the server.
4. Deleting the account and setting it up again from scratch does not solve the issue and will result in the loss of all the email placeholders - further increasing your loss of knowledge.
5. Switching the account to IMAP if you go for a delete and re-setup will also result in the loss of all the email placeholders but will 'probably' solve the problem (within the limitations of IMAP) for future emails.
6. this affects all iOS devices - iPads (all gens on iOS 9) iPhones (all gens on iOS 9)
7. This affects you irrespective of you country, internet provider or email provider - the discriminator is the use of pop/smtp.
8. pop/smtp is not legacy or backward compared to imap it is just different. We use pop/smtp for 3 reasons: we don't want emails left on the server where a questionably secure environment could be compromised; our family want the ability to all download the same email to multiple devices without affecting each others ability to do so; we want one master device (the main iMac) to be the deleting device that holds the archive of all emails (right now we are very pleased we have this as all the iOS devices are scorched earth right now).
9. Some emails appear unaffected - I cannot identify any rhyme or reason to this. Old, new, addressee, - there doesn't seem to be a pattern. Can't say for certain but it seems that more are being affected as time goes on. If you are affected and you have the only copy of an email currently and you are going to need it again.....get it somewhere else ASAP!!!
10. This thread and forum is just for sharing knowledge between users. If this has affected you then you need to fill in the apple feedback page with your confirmed symptoms and the impact if you want anything to be done. Follow this link and do it now or apple pop users remain without a fix! I recommend do one for each type of iOS device you have affected and the mail app itself.
http://www.apple.com/feedback/
OK other threads - maybe someone else is familiar with a clever way to link them all up - please do so if you know how:
https://discussions.apple.com/thread/7226924
https://discussions.apple.com/thread/7221489
https://discussions.apple.com/thread/7226501
https://discussions.apple.com/thread/7227219
https://discussions.apple.com/thread/7230143