Sprocket, something else you might want to try here... It might not stop the replication of the cookies, but it could tell you what the offending application / website is:
In Internet Explorer (this is where you set it, even though you're using Explorer), click Tools -> Internet Options. Select the Security Tab. Click Custom Level and scroll down until you come to the Cookies option. Set these to "Prompt" and delete the stuff you did previously. Also ensure the Cookies folder is empty.
It might not get rid of the problem, but it should give you some idea as to what's causing it, as you should be prompted to load up cookies etc.
Hope this helps