Hi Chris,
I've to agree with Greg, what you describe sounds very much like you are using the POP3 protocol on your phone with k9 to fetch your email from your server.
POP3 by default will download the email to your client and when retrieved the copy on the server will be removed.
Please check your settings in K9 for the account in question.
In the account settings look for fetching mail and then incoming server.
The first row should read IMAP server in its title.
When you can confirm IMAP is set up in K9 then further investigation would be required.
I've been using IMAP for many years with various clients on my phones, and various computers
and have not had issues as you described.
Best
Martin