State Management :: Identify First Or Second Time Visit To Website

I work in a multi server , multi webfarm environment (without sessions). We need to be able to identfy if a customer has arrived here for the first or has been before (even though they have not logged in)Not only will we change the text of our salutations depeding on this state but we will also use it in other busness logic. I can check for the existance of a cookie when they fire the Session_onStart event but I would have to write a cookie out to show they had previously visited for the next time the customer came to call.

If I wrote the cookie out in the Session_onStart then somehow I would have to tell the website that this was a first time visit. Also as this is a stateless webfarm - the next server may be different from the previous one which would fire a new Session_onStart event in its own right - which would see the cookie and assume it was not my first visit, even though it was my first visit on a different web page of the web site.

I dont want to write it out and say if its within X minutes of the cookie creation time you are still in your first visit as that x minutes wouldnt work 100% of the time If I dont write the cookie out on Session_onStart then when could I write it out?