An alternative to this dependance on cookies is to build a custom session handler, which you call from the top of each page. This custom handler can just use cookies for anyone who has then enabled, otherwise it can pass a sessionid as a GET/POST var.
I've done this successfully in the past. You can also use this custom code to caclulate a "confidence" score for any session id - by logging the IP address which last used a particular session ID, the time when it was last used, the last session id used by the currently requesting IP etc etc.
All in all, it's possible to build up quite a healthy system. But what everyone else is saying is important too. You may find that it takes you some time to develop this flexible session handler, and that time may be better spent on other functionality which you could be adding to your site.
On the other hand, if you invest that time once, it could be something you can quickly add in to future projects, making them all more tolerant and respectful of user settings.
The choice is yours 🙂