Not so much a "problem" but more a reflection of how shitty POP3 is for mobile (limited sync) use.
But I'm not very clear on this one:
If they make it to deleted items and I empty the deleted items folder, then they never seem to come back, but every so often I have to go back and delete a couple hundred emails that I know that I previously deleted
So if you empty the deleted folder, they don't come back.
In what case then do they come back?
If you move messages to Deleted and just leave them there, not emptying the folder?
How many do you typically leave there at a time, dozens, close to a hundred or more?
And how many new messages do you receive per day, roughly, dozens, close to a hundred or more?