For Messenger Service ads:
You need to install or enable a firewall:
http://support.microsoft.com/default.aspx?scid=KB;EN-US;Q330904

Disabling Messenger Service can be a good idea, but it does not solve the
real problem.

The ads are not the real problem, the ads are only a symptom of a larger
issue.  The real problem is open ports that allow unwanted traffic into the
computer.

Disabling Messenger does nothing for the open ports.  You would need a
firewall that controls the traffic.

The above solution will not work if you have AOL as is not compatible with
Windows XP Internet Connection Firewall (ICF).  If you have AOL, you should
contact AOL and/or get a 3rd party firewall.

Disable Messenger Service:
Start/Control Panel, click Administrative Tools, click Services.
Go down to "Messenger".
Right click "Messenger" and select Properties.
Hit the Stop Button under Service Status section
Then under Start-up select DISABLE
Click OK and follow prompts

Check this link:
http://www.aumha.org/a/noads.php
Run Ad-Aware (free version) or Spybot to check for spyware:
http://www.lavasoft.de/
Or
http://spybot.eon.net.au/

For internet pop-ups, try one of these:
http://www.panicware.com/
http://www.bysoft.se/sureshot/stopthepop/index.html
http://www.popupbuster.com/PopUpBuster/
http://www.kolumbus.fi/eero.muhonen/FS/
http://www.endpopups.com/
http://www.adshield.org/