Bugger! I have a similar issue. I use two different devices to access my emails, Microsoft mail on my PC and the native app on my phone. I've recently had the issue of various emails disappearing from my PC but still being on my phone. I have been informed this can occur when one of the email clients is set up using pop instead of IMAP so it was suggested I back up my emails on my phone, remove the old account and set up a new IMAP account, then re-store those emails on my phone from the back up.
My emails are still held on the server though, so if I've read this correctly, I could remove the POP account from my phone, reconfigure an IMAP account on my phone and simply sync my phone with my email server to restore my emails.
Can anyone please confirm if I have understood this correctly or if there is more to it?