From what I know, firewalls generally don't block spyware/adware/malware - at least that isn't their primary function. Firewalls are primarily meant to restrict unauthorised access to your system by monitoring certain data traffic and closing and "stealthing" certain data ports used during Internet usage that would otherwise be open and vulnerable to hackers and unauthorised scripts.
Unfortunately, thanks to the nature of the Internet, a lot of spyware can be accumulated from web browsing and is part of the traffic from the website and, as such, isn't filtered by firewalls. There are steps you can take to help prevent getting spyware and malware though.
Firstly, make sure you're using the removal utilities correctly. Sounds stupid I know, but I've encountered many people, especially those who use Adaware that run the program, find entries but then don't select to remove the entries, so they just stay there until the next scan. (With Adaware you have to make sure the check-box to remove the entries is ticked which you can do by right-clicking a single entry and choosing "select all"). Also ensure to keep all your Spyware programs up to date.
Try also "SpywareBlaster", free from Javacool Software (
http://www.javacoolsoftware.com/) this program doesn't remove spyware but helps prevent it from initially installing.
If you use Internet Explorer (which is very vulnerable to spyware thanks to its popularity) try using an alternative. Good ones are Firefox and Opera. Neither of these programs use ActivX and, as a result, you'll rarely ever get that box pop up asking if you want to install software.