This actually only happened after an e-mail server ran out of space due to run away log files. Normal Desktop clients were not affected. It appeared to be a bug in K9 mail but even reinstalling/wiping all settings did not fix it (read e-mails would still not reappear).
This is moreso a bug in Dovecot where it probably messes up the index files.
How do you fix this in Dovecot/your e-mail server?
You need to delete the dovecot index and related files so they can be rebuilt. Note if you have a lot of e-mails and a Desktop client this will force it to redownload all e-mails (possibly thousands or more for some users). But it is the only way I could fix the issue in my K9 Mail Android client.
cd /var/spool/mail/yourdomain/youraccount/Maildir/.yourfolder
#Backup dovecot files
mkdir 00-dovecotbk
#delete dovecot files
rm -rf dovecot.*
android, mails, dovecot, server, solutionthis, desktop, appeared, reinstalling, wiping, settings, reappear, moreso, messes, index, delete, rebuilt, redownload, users, var, spool, yourdomain, youraccount, maildir, yourfolder, mkdir, dovecotbk, rm, rf,