you can try using adaware, it's a free software that will take off the spyware on your computer.
Your other option is to disactivate the message service from windows, note this does not affect msn messenger.
go to control pannel, then to system tools, or service tools, not sure what it is in english, then you go to services. You disactivate the mesage service, 4th one on my list but this version of windows is in french.
Disactivate it and you shouln't get anymore pop ups.