If you now mandated them to respect some special HTTP header instead, most of them would simply 403 all browsers with this header set and you would have to disable it to access these sites. So same thing as with JavaScript and cookies - either tolerate crap or stop using a dozen websites or install yet another extension for management of per-site exceptions.
This law is silly and completely detached from reality. They should either prohibit tracking by law or do nothing.
A number of websites formulate this as "By continuing to use this website, you agree that we will access your cookies," accompanied with a "Dismiss" button, but that's not really what the spirit of the law is.
DNT didn't change anything to this, as it was meant for a completely different use. I'd even say using DNT for this is a complete hack, which sort of misses the point of both the cookie law and DNT. You are, however, completely right that it is stupid beyond ridicule that you technically can't store the fact that a user doesn't want cookies on the browser.
Edit: paragraph formatting.
[1]: http://ec.europa.eu/ipg/basics/legal/cookies/index_en.htm#se...
Yes you can, it's pretty simple to do. Add a timestamped entry into your database to not show that notification to the IP address the user comes from, then run a script every minute that clears out entries older than an hour. Granted, if you go back to the website an hour later, it would still pop up the request to access cookies but it certainly beats having it pop up on every page load.
How about a browser extension that hides any overlay divs with the string 'cookies' and input buttons?