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 do........