Same problem when using the native Email app that comes with my Anrdoid phone (the app name is just "Email"; see image above). I use gmail, so my solution may only apply to gmail users.
I found the answer here:
Read Gmail messages on other email clients using POP
After visiting that link, scroll down to the "Troubleshoot problems" area, and click on "I want to download emails on multiple email clients". There is a #1 and #2 in that section, but I only needed to do #1.
In case that link breaks in the future, here is what I did:
When creating a new account in the Email app, add "recent:" in front of your email address like this:
recent:example@gmail.com
When I do this, my emails are NOT deleted from the server, which means that I can still use Outlook on my desktop PC to get my emails like normal.
FYI:
In the Email app "Incoming settings", I do have "delete email from server" set to never, but the app still deletes email from the server. Adding "recent:" in front of my email address during account setup as described above solved the problem for me.
My gmail settings for POP are set to "delete gmail's copy" when messages are accessed using POP.
I prefer to use the native Email app, since I only casually check emails with my phone; it's not my main way of emailing. Also, using it means I don't need to download yet another app, and one less app that needs to keep updating itself.