Smokeball, perhaps you can advise him to set his antivirus software to "delete on sight" rather than "quarantine." Another possible solution would be to uninstall Outlook Express completely (use Add/Remove Programs in Control Panel and hit the Windows Setup tab, if it's Win98). Then it could be reinstalled with a quick visit to Windows Update.
Perhaps he could simply delete the message store which contains the Inbox emails... does anyone know what type of file he should look for? It doesn't appear to be a .pst file, since I just installed Outlook Express and it doesn't create a .pst like Outlook does.
With our McAfee antivirus, some extra options are also added to Outlook's "Tools" menu, including being able to set up preferences for a manually-triggered scan of the Inbox. Perhaps Norton has something like that too. It's going to be a bit frustrating trying to help him over the phone, I suppose... good luck!
edit: for the record, our work systems do a daily scan of everything on the hard drive, including the Recycle Bin where Klez may try to set up base, and the reason the network drives aren't included is that the server does a daily scan at 3AM and also checks all files upon read/write/rename/etc, as do all of the client machines.

I'd rather be safe than sorry, since we work with very sensitive information (among other things, my co-workers counsel sexual-abuse and rape victims) and Klez has that scary ability to randomly email documents. :Q