I also second (third) the recommendation to investigate switching to IMAP.
From your description, it sounds like your POP3 mail server may be indexing messages in reverse order (not by date, descending) -- and that's why the app is downloading old ones, instead of new, messages.
But one other thing to check while you're still using POP3 -- if you use "Move to deleted", you will want to long press the [ Deleted ] folder and "delete all" from time to time, so it doesn't grow too large. Note that this will delete any messages currently in [ Deleted ] from the mail server.