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