After teh windows update, you probably had to reboot. Alot of times, if you dont have it completely removed, spyware reinstalls its self when you restart your computer. As far as losing your cookies - usually for me at least anyway, most of what adaware removes is cookies. Main thing you need to do, in my opinion, is find out exactly what you have. For instance if you have coolwwwsearch or one of its variants you can get cwshredder to remove it. Also some aspects of spyware need to be removed in safe mode. I always remove serious spyware in safe mode. Then reboot a couple of times and make sure it doesnt get reinstalled. If you really cant get rid of it, check out "hijack this" at (link) Its will create a log that you can post on their message boards (forums) and someone will look at it, and tell you what the problem is. Dont remove anything hijack this finds without knowing what it is though because most of it, you need for your compter to work properly.
I would try running adaware first. (make sure you update it everytime you run it) Then run cwshredder (available at same place as hijack this) because it or one of its variants is the main thing that adaware doesnt completely get rid of. Its the problem with 90% of the peoples computers that i fix because they had spyware. Even if you dont have cws related spyware, it cant hurt to run it. Remember to run it in safe mode if it finds anything to be sure to remove it all.
I also highly recoment firefox and thunderbird. I switched to both a couple of months ago beacuse i couldnt find a way to make internet explorer secure. I do use IE for times when firefox is having trouble with a particular site, but its good with 98% of the sites i go to. Spyware is too easy to get in IE these days without you even clicking yes on a security warning. I actually have tried to get spyware with firefox and was not able to. Its alot like internet explorer, more than any other alternative browser, and has popup blocking included.
Between doing the above, being careful what programs you run, and being careful what you click yes on, you should be able to avoid spyware for the most part.
Good luck,
-Dave