The virus tools I have (AVG) only pick up the threat when it is moved into the deleted items folder.
Time to get better antivirus software. Or get your scanning done server-side (which is really the best way anyway).
If I set a message filter to "remove from POP3 server"
No. It won't.
POP3 is an offline protocol.
It pulls the message off the server and you read it locally.
The "remove from server" allows you to save space on the server by deleting the message once it has been downloaded.
Some people don't use this if, for example, they have multiple machines and want to be able to download from multiple machines. But then those people should be using IMAP anyway, as POP3 leave on server has never been very reliable ! (and no, IMAP won't do what you want either)
Hope this makes some sense !