Usually you don't need to format your harddisk if you know how virus works.
You can goto http://www.nod32.com
download a trial version Nod32 to see whether it can help you get rid of this virus.
NOD32 is a better antivirus software,comparing to NAV, Macfee.
If it still can not help, I think the last thing you can do is to install The Bat!
another almost perfect email software, It can import msgs from outlook express, so you won't loss your old msgs., after that, you can delete your Outlook Express
Good luck!.