With POP3 email there is an option to leave a copy of the message on the server. This option is useful for when you check your messages on your phone but still want the originals to show up when you check your Outlook. I believe this option is set by default on Android.
If you delete the message locally on your phone it's still kept on your email server so Outlook can retrieve it. Once Outlook retrieves it, however, it would normally be deleted from the server. In this case it sounds like the messages are being left on the server indefinitely and your email client is "forgetting" that it's already downloaded them once. This might be an issue with your email client.
One way to find out for sure would be to go onto the Android Market and download a third party email client like K-9 mail, configure it, and see if the problem persists.