There's a fairly simple solution for this IMAP deletion problem. Set your e-mail view not to display items once they have been marked for deletion. This will make it appear as though the message has been removed from the server.
When you feel ready, permanently delete the items by purging them.
For your case the best would be web based. If you use pop accounts set the files to remain on the server for a set number of days. So deleting them on one pc will not remove it from the mail server. That way it will still be on the server when you check with your other pc. You can also set mail systems not to empty the trash on exit.
I go back in forth between to pc's. I leave the mail on server for 2 weeks. The only problem I run into is sent mail. The sent folder only remains on the pc that sent it. But my web mail account all is there. If you get enough storage space you do not need to worry about cleanup. Now if you are over run with SPAM, I would change emails and keep it private.