I use Zonealarm and only prob Ive had with it was one particular TeamSpeak (voice comms) server, I guess it didnt like the port the server used, other than that no problem at all - and even that TS server was ok after I either set security to medium instead of high or on suggestion of zonealarm guy, added TS to trusted (might need the pro instead of free version to add programs to trusted though, not sure). Zonealarm has a excellent free version and eats 4mb of your ram - well worth it.
A slightly dubious-looking but actually good site for testing your firewall, and some other fiddles is
http://grc.com - I wouldnt bother with his little apps though, you can do the same things manually with tweaks from e.g.
www.tweakxp.com
AdAware is good, especially for ease of use, but
Spybot Search and Destroy is even better - but requires a bit more knowledge to work safely. I originally got it because Ad Aware appeared to be not getting updated anymore, but a new version should be out very soon.
Also worth having a fiddle with XP services - not only to free up some ram but kill some dodgy services. Ive never had a messenger popup because for week 1 of getting XP i disabled it on advice of excellent XP serive tweak site
black viper.