Decent overview of the problem of cookie deletion from the NY Times (registration required), which lays the problem out without ever really answering it:
Eric Peterson, the analyst who wrote the Jupiter report, pointed out that most of the deleted files were so-called third-party cookies placed on the computer by a company other than the one operating the site the user was visiting. Most publishers rely on outside companies like DoubleClick and Atlas to send ads to the user’s computer and track the effectiveness of campaigns.
Antispyware programs often leave in place first-party cookies, which can save users the inconvenience of having to log in to a news site each time they visit, but remove third-party cookies, the main target of users’ ire. Some people say they think that total anonymity is the way to go.
For what it’s worth, I think this is a user interface problem. Cookie management has always been well and truly hidden inside a browser’s menus, which only encourages users to think it’s something “techie” and complicated. And decent explanations of what cookies actually are are few and far betweenn (for what it’s worth, here’s ours).
Like lots of issues to do with online marketing, I think this is all about an implied contract between a web publisher and a user. The contract reads something like this: “In return for providing you with content, I will put advertising alongside that content. In order to do that effectively, I need to use technology fairly and effectively, which means you let me put a cookie on your machine. Here’s how your privacy is protected, and here’s how my business is protected.” The key problem is that no-one, and I mean no-one, has been able to come up with a usable interface for describing that contract to users as they are using the service. Crack that, and you crack the cookie “problem”.