As far as I recall, the EU cookie law is a bit more global than that: a website needs to get permission/consent whenever it wants to store/retrieve information from the visitor's browser---this isn't just limited to tracking. This means that every single website hosted in Europe/targeted at a European audience need to request the authorisation to use the user's browser storage.

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.