On your PC, are you getting your email using a web browser, or are you using an email program? If so, which program?
Also, to clarify, when you say change to using IMAP for Gmail, do you mean change it on the iPhone? I've found that whenever I want to make any major changes to my email account settings on my iPhone, I usually just have to set-up the account again.
I agree that if you could use IMAP instead of POP3 (for both accounts), that should do a lot to solve your problem. Does your domain support IMAP?
For Gmail, there is another option you can use instead of POP3 or IMAP on the iPhone, if you are interested, you can use Exchange ActiveSync, which I find works really, really well, especially if you want access to your Gmail address book from your phone. See http://www.imore.com/2011/02/16/beginner-tip-setup-gmail-exchange-push-emails/