I used to remember that for stubborn spyware or unknown cookies, I would search the name in the Windows registry, and delete the registry entry. This would eradicate the cookie for good, but careful doing that lest you bugger something else up.
CCleaner is good, but it is out of scope for an ubercookie backed by malware. Check out a couple of malware removers-- I like Spybot Search and Destroy (but many anti-virus programs come with malware tools). The border between malware, spyware, and virus is pretty grey so it doesn't hurt to have one AV program that does malware, and one dedicated malware remover.
It's a little old school, but I don't use Windows for work or play. Of my Windows using family, friends, and women I date, I move them over to a 'standard stack' and Spybot is part of that stack. When you get stuck being other people's computer guy the most important than is to get everybody on a common stack. It doesn't so much matter what the stack is, as long as it works, and YOU know it.