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.
#Backup dovecot files
#delete dovecot files
rm -rf dovecot.*