i personally think that using a combination of sessions and cookies always seems to work.
for example, its not insecure the use a cookie to store a username, but (obviously) not a password. so when the user gets to your site, the 'site' recognizes the user (based on the cookie). after you've verified that user, you could add a session to 'tell' the 'site' that this user is valid and allow the user to access 'member only' pages or whatever.
now back to your question......
could it be that 1 particular file is causing the problem? maybe it doesn't have session_start() on that page or a session is misspelled. You could alternatively store some information in the mysql db (and maybe in combo with my spiel above).
you must also remember that the session is active as long as the user is active. (i'm not sure of the session active time though, could be 10 min), so if a user is reading a document and it takes him/her over 10 min to read and he/she tried to get to another page on your site, that session would have expired, even though the user was still 'active'.... follow what i'm saying?
i obviously could be slighly wrong, but that's my view on sessions, mysql and cookies. 🙂
hope that helps.