SpySweeper and SpyDoctor (both payware) are much better alternatives and from what I read if you use both almost 100% of malware is removed!
As far as using a firewall I agree that it is IMPERATIVE but I find Windows Firewall does a good job at it provided you avoid suspicious downloads, p2p software and hackware sites.
Regards,
Nick Magos