Very strange, if you regularly clear out the folder on the server then it should not be possible for Outlook to redownload those messages. My first thought was that you had somehow created a 'smart folder' or something like that, which is essentially a folder filled with links to e-mails stored in different folders. The fact that they appeared to download doesn't tie in with that though. I have had Outlook redownload stuff at times but that was usually after a reinstall or when the indexes on server and PC had gotten out of sync.
Sorry, I'll have to pass on this one, over to another genius please!