What Kentico Version / Hotfix are you on? This may be a bug that has been fixed.
Additionally, are you storing Session InProc (default), are you hosted in Azure or on a physical machine? Session handling may have an affect on this (probably not but just checking).