Are you sure you didnt accept the sponsor prog in Messenger Plus!? If so unsinstall Plus!
Try looking for a folder you think wasnt there before or something. Last time i got spyware it was stored under 180sol forlder in Program Files.
Try:
Spybot S&D
Ad-Aware