Depending on how busy your site is and how willing you are to re-write your cookie code, maybe you can just bypass cookies altogether by taking a browser fingerprint, sending that up the tubes and using that information to setup sessions. The session id can subsequently be placed in the URL for future reference. To get the fingerprint you could MD5 the browser fonts, plugins, screen size and other javascript accessible guff.
Here is the EFF page on how to track browsers without using cookies:
http://www.eff.org/deeplinks/2010/01/help-eff-research-web-browser-tracking
Naturally you can reverse engineer that code from the frontend side.
Another option is to store the unique identifier in an image, e.g. the store logo. Or the browser history URLs can be looked at, as per those sites that know if you have been to 'example.com'.
Naturally your detection code can be obfuscated by putting it through the closure compiler.
These 'cheats' do need scripting, but only Windows Server admins have that turned off, don't they? Nonetheless, some plan B will be needed...
You can geoip your site visitor so that you only need worry about the cookie problem if their IP is in one of the EU countries.
Only if you cannot automagically identify your EU visitor would you then need to degrade gracefully to cookies - and asking for them. Naturally you'll be wanting to do that with a huge un-bypass-able modal dialog-box showing the Cookie Monster hugging Peadobear asking how you wish to be stalked today obviously to the tune of your favourite Rick Astley song - that should help with conversions...
Yep, this new cookie law is silly, but cookies were never intended to track people in the first place, were they..?