Using procmail to block the messages would probably be the best solution. The kbase docs on procmail are (sadly) a bit out of date currently - updating them is on my todo list. Also, using procmail takes a bit of technical know-how, so it's not a good solution for many people.
Using IMAP might help, since if you recognize the message by its subject line, you could delete it without actually downloading it from the server (POP3 requires you to download it).
If you use PINE or mutt for mail (on the machine itself), you have the advantage of not being able to get the virus, and you can delete it very quickly / easily.
Another suggestion would be to read the headers and report the message to the ISP of whomever (presumably unintentionally) sent you the virus -- you might even be able to guess who sent you the virus and let them know.
I'd eventually like to provide some rudimentary virus filtering capabilities to customers (server side), however this is fairly difficult to do on a large scale, since processing that much mail is fairly resource intensive.
We did start using a virus scanner on the office mail server after some Outlook (ugh) using employees got viruses.