There are programs / tweaks that remove Windows Messenger ... http://www.theeldergeek.com/messenger_removal.htm
http://www.winguides.com/registry/display.php/989/
http://www.dougknox.com/xp/utils/xp_mess_disable.htm

which virus are we discussing here? Bound to be a way of getting rid of it without resorting to a reformat.

Hugh