It is next to impossible to nail down the cause of a problem without steps to reproduce it, where the error only occurs sometimes for some people and not all, the first thing that comes to mind is an issue on the server with session garbage collection. It cold be that the server is emptying the session temp files from the php temp directory prematurely.
For each session that is started, a temp file is created on the server, this file is used to track the contents of the session and is deleted when the session expires, or the user closes their browser, the server may be deleting these temp files before it is supposed to.
It could also be that the user is crossing domains. when they first arrive at the home page, they are coming to:
index.php
it is possible that the add to cart button is forwarding them to:
cart.php
these would be considered two separate domains by the session cookie, so the cart would appear top be empty. the item was added to the cart page for the domain:
cart.php
instead.