From what I understand, you had Windows Live Messenger 2009 beta and its forced an upgrade to the latest version. That process should of been simple and it is not a trojan, so the trojan you found wasn't related to the Messenger upgrade. It must be something else, unless you downloaded a fake dodgy version of Messenger from somewhere, which I doubt.
Try removing WLM from Add/Remove Programs. If you can't, try
ZapMessenger.
/ 
