I am trying to do the same thing.
I tried IMAP and I understand exactly what it is and used it in the past but I want it simple without all the IMAP directories since I also use Outlook for Exhcange. I know I can hide some of them, but deleting the messages from the inbox in outlook did not remove it from the archive or all folder on the gmail server. I then tried to delete from the all folder in Outlook and it put a line through it which I hate, but I tried it anyway and then had outlook purge the messages and it still didn't work right deleting it from Gmail.
Erwin I think I found out a way to make it work with POP exactly as you and I want. It is currenlty working for me but the real test will be if the messages still exist on the server after 30 days.
Set up gmail with POP enabled and to keep Gmails copy in the inbox.
Now go to outlook where you configure the POP account (Tools, Account Setting, Change) and in the username field put recent: infront of your username. recent:username@gmail.com
Go to more settings Advanced and make sure Leave a Copy of Messages on the server is checked and remove from the server when deleted from 'Delted Items' is checked.
This appears to now be listening to the delete command from outlook and removing from the server when I want it to and it is not in the All mail either.
I found out about the recent setting here.
http://mail.google.com/support/bin/answer.py?answer=47948
It is supposed to keep messages for 30 days and then removed pop ones. I hope it does not remove them since the setting for pop is set to keep gmail messages in the inbox.
Let me know if this works for you.