The problem is with POP accounts -- I have no idea if IMAP also have problems.
It seems that not only must you have a constant connection, the messages must still be on the server *in the inbox*. If they've been moved or deleted, they become "this message has not been downloaded" -- even if they *have* been downloaded, possibly more than once.
This started when iOS 9 came out. POP worked just fine for years before that.
It seems as if Apple has tried to IMAPize POP accounts in its iOS mail app. They also added a couple of settings that look like IMAP-wannabees -- e.g. a choice to 'move message to Archive', except that the messages disappear from there too, leaving only the headers & dreaded "not downloaded" statement. Not what I'd call an "archive".
I'm just glad I've never depended on Apple for my mail-processing; I just use my iPhone to read over messages, see what-all's there, flag some to deal with later. At least having the headers flagged remind me of which ones I need to attend to first -- from my PC.
Maybe it's time to change my workflow habits again, but it sure has been nice these past few years to browse new messages and look over old ones (often w/ handy links in them) and ponder/remind myself what I want to do with them -- from the comfort of my recliner.
I did submit feedback to Apple but of course do not expect to hear anything back from them.