Earlier quoted context omitted.
Simple solution: put a persistent cookie on the computer of everyone who's ever logged in. Automatically log the user in if this cookie is present and the URL is correct. Obviously, the cookie should be unforgeable - e.g. HMAC-SHA1(service_secret_key, username).
The only situation you're targeting, then, is when a user intentionally logged out (in non-privacy mode) in the past (because otherwise they wouldn't have the half-cookie). Is it really desirable to log in them automatically in such cases? But then if they're clicking on the link in the first place, one might conclude that they desire is to log-in, so it's just added convenience. However is it legal under the new EU…
I'd expect this to be legal - set the cookie on login.mydomain.com and never use that domain name for anything else - but IANAL.