You can also get some really good utilities at Karen Kenworthy's Site.
http://www.karenware.com/
Two I use a lot are 'Cookie Viewer' and 'Registry Pruner'
I also use 'Registry Ripper' which will allow you to search the Registry for a 'string' and then save the found Registry Entries out before deleting them.
Diane and the rest can check these out and make appropriate recommendations.
Ad-Aware may be the best choice, though. 'Pest Patrol' is also pretty good and has a trail version that may cure this one.
Reg-Pruner finds and allows deletion of registry Entries that no longer have validity.
If you find the sub-directory something is hiding in and can delete it. reg-Pruner gets rid of the registry entries that were associated with the deleted sub-directories.
Re-Ripper on the other hand is a Search and Destroy for registry entries. WARNING: YOU CAN REALLY TRASH YOUR SYSTEM WITH THIS TOOL!
But, for Reg-ripper to work you have to know what to search for.
This doesn't sound like a 'Cookie', IMHO. it sounds like a rogue program (virus or trojan) has added a registry entry to check if it's still active, and, reload itself if it isn't. Usually, the source to reload from is named something entirely non-obvious.
Ad-Aware and Pest Patrol are usually pretty good about having the names of these items...
I use 'Zone Alarm' and NAV (Not the full utilities set) and so far I've been 'secure'.