Well, the thing is... what do you want the firewall to do?
Filter incoming connections? Even XP's integrated one can do that, and if you want filter rules that it can't do (like banning IPs and not just port-based rules), you can use the IPSec policies which are in Windows since Windows 2000.
Filter outgoing connections, preventing trojans from communicating with the outside world? Forget it. Many trojans know how to circumvent or disable the firewall. If you run malicious software with admin rights, it can do whatever it wants. And if the deinstaller of the firewall can remove the firewall, why should a trojan NOT be able to?
So in other words, you have to stop working and surfing with admin rights and use them only for software installation. Before you do it that way, you don't even need to THINK about personal firewalls - they just won't help you.
And even without admin rights, there are always easy ways to circumvent the firewall. When I want to get data out of the system, I can get it out. Simply by abusing the web browser you surely have set to "don't ask, always allow". Starting it with an URL, editing the bookmark file or the start page are the usual tricks, but changing proxy settings is also a possibility - and personal firewalls don't detect all of them and never will (catching all that stuff would render your system unusable because every few seconds, a personal firewall dialog will pop up).
So the only solution is - don't run malware. If you don't run malware, you don't need a personal firewall. Instead, just use a packet filter for incoming connections (like the one integrated in XP, ipfw or Win2k's IPSec filter rules) and disable unneeded services (
http://www.ntsvcfg.de/ntsvcfg_eng.html). The latter will also free up some RAM and in the end make your system faster.
A virus scanner, however, doesn't hurt, so install one and keep it current. Kaspersky for example is supposed to be one of the best when it comes to the signature files. Just remember one thing: it is highly possible that you get a virus before the virus scanner knows it. DO NOT CLICK ON EXE FILES ATTACHED TO EMAILS. EVEN IF YOUR VIRUS SCANNER DOES NOT COMPLAIN, IT DOES NOT MEAN THAT THE FILE IS CLEAN. Use your virus scanner to filter virus mails from the inbox, these are spam anyway and a virus scanner can reduce the spam without doing any damage/false positives. Also, use the virus scanner as "last resort" in case you or someone else accidentally click on an untrusted EXE. There is no guarantee that the scanner will prevent an infection, but it will catch SOME of the cases.
Also note: not just EXE is evil. Also watch out for VBS, JS, COM, PIF, BAT, CMD, SCR and any other extensions that stand for executables. An attachment named "www.foo.com" is most likely NOT an URL but an executable whose name looks like an URL to make you click on it. Note the extension "COM". If you want to look at the URL, enter it manually in such cases.
1. Open Notepad
2. Paste: ÿþMSMSMS
3. Save
4. Open the file in Notepad again
You can vary the number of "MS", so you can clearly see it's MS which is causing it.