Actually did this with both my Hotmail and my Webmail.godaddy.com accounts. I now know how to tell it not to delete the emails in the future but can't seem to figure out how to replace the ones already deleted and now only available on the computer with my Evolution account on it.
What you're really wanting to do, if possible, is switch to IMAP instead of POP3.
If IMAP is available on your mail servers you could try this:
That should copy them back to the mail server. Personally I'd stick with IMAP instead of POP3 (I use IMAP for all my accounts) as it's more aimed at storing the mail on the server whereas POP3 is aimed at downloading the mails to the client computer.