the addresses of the stores/EBay, whose search engine were you using?
Google or Yahoo's or? Is you ISP contractually connected to Yahoo?
(mine: Rogers cable is particularly for mail). I expect Yahoo is tracking your inquiries and passing on the info or their suggested similar findings to your search and one of the recipients paying for that info is sending this basic trojan at you via/thru a hole in Messenger. This agent is like a doorman standing at you backdoor.There is also a back door messenger route hiding in Outlook Express (if you have such on board). Assuming Win XP SP2 or better...(you don't say)

"Windows NT, 2000, and XP hide an hidden Internet server that is running by default. It receives and accepts, among other things, unsolicited network messages that cause pop-up dialog boxes to appear on the desktop. Internet Spammers have discovered this and are spraying pop-up Spam across the Internet." GRC.com

If you don't really NEED Messenger, there is a free program called "Shoot the Messenger" to block this path from GRC about 1/3 way down:
http://www.grc.com/freepopular.htm

I would also NOT put it passed some shopping stores/sites to be including it thru cookies your allowing them to place on your machine.

Many TOOLBARS also may be allowing entrance to your machine. I refuse to allow any toolbars, period.

Using a Free Mozilla browser (requires Java)(even better w/ Free NoScript add-on) would allow you to limit those cookies to session only (deleted from temp after leaving net)or deny totally. No Script will show a list of the scripts/cookies attempting to download at each site and offer above limits to each individually. (One may consider this a toolbar, I just consider it a tool).
http://www.mozilla.com/en-US/firefox/firefox.html
NoScript for FF:
https://addons.mozilla.org/en-US/firefox/addon/722


Free CCleaner (Slim version bottom of page) will clean out those cookies at each running after leaving the net as well:
http://www.piriform.com/ccleaner/builds

Hope this helps. Happy