@mariel, your issue seems to be related to using some sort of caching mechanism…. Are you using any Caching plugin (eg. WP Super Cache)? If you are then you may want to checkout this page:
http://www.tipsandtricks-hq.com/ecommerce/wp-shopping-cart-and-wp-super-cache-workaround-334