first, lets double check that the server is properly configured o set and save session information.
the following thread has a sessionTest page attached that con be used to test the server for properly maintaining session state:
showpost.php?p=23826&postcount=2
if the test fails, you will need to contact the host to have them correct the probelm, most likely, it is a bad session.save_path setting in the php.ini file.
if the test passes, please send a copy of the add to cart page so i can examine the code.