Have you setup forms in web.config to enforce the use of cookies? (cookieless="UseCookies")
I have seen cases where outdated browser definitions caused ASP.NET to believe that cookies cannot be used. You can easily test for that in a simple application. One time even IE10 wasn't supported (because ASP.NET only tested for IE1..IE9), but there was a Windows Update for that.
Cookies may also be rejected for several browser policies, for example by invalid hostnames, for example if it contains an underscore.