Just ask me (the user) for permission and explain why you would like to do so.Unfortunately, it's not that simple.
From a user's point of view, asking questions that interrupt their browsing experience on every other site is usually unwelcome. The "We use cookies (like everyone else in the known universe)" messages in Europe that you mentioned are a great example, where good intentions ran headlong into practical limitations and the result was something that no-one actually likes.
From a business point of view, that same poor experience is a negative because it makes your site less attractive to visitors and ultimately hurts conversion. This remains true even if you're doing something reasonable with innocent intentions that almost all of your visitors would actually be happy for you to do.
I am very much in favour of protecting privacy on the Web and letting users make informed choices about when they are willing to give it up in return for something they value, but I don't see this working in practice until we have some sort of mandatory (with force of law) standards for disclosure by site operators that allow browsers to offer standardised preferences to their users that can be set once and then safely forgotten about. I think we need some sort of standardised, automation-friendly privacy policies, like the credit agreements where providers are required to provide key information up front in a standard format with the same assumptions for everyone, or the way a few open source licence agreements have become established and much of the time both the licensor and the licensee can just say "GPLv2" or "BSD" and everyone knows the deal.
Unfortunately, the wheels of standards turn slowly, the wheels of law more so, and the wheels of laws respected across borders even more so. Meanwhile, the wheels of businesses funded by invading privacy or otherwise exploiting users via modern technologies tend to turn very fast. I'm not sure how we fix this problem as long as the politicians are as technically illiterate and generally open to manipulation by special interest groups as they obviously are in many first world countries today.