Set up outlook to use imap instead of pop3. Pop3 is intended to actually remove messages from the source server when you first download them, and doesn't work as well when you want to access your message in several different ways (ie, from both outlook and the gmail web interface).
Pop3 was popular for a long time because of the small size limits placed on many mailboxes and because you can still read the messages when offline. Now that most of us have an always-available connection at home and the mailbox limits are more inline with actual e-mail use (gmail allows over 7GB now), imap makes a lot more sense.
Just note, though, that gmail is a little different for imap. You get to choose whether deleting a message in outlook archives it or deletes it on the server.
If you have a Google Apps Premier or EDU editions, you can use the relatively new Google Apps Sync tools, found here: