This is one of the strangest problems I ever encounter...
How to simulate the problem:
1) In your WP settings, use a non-default permalink setting
2) In your WooCommerce settings, tick "Clear cart when logging out"
3) Open your website using Firefox. Pretend you're a first time visitor. Add an item into your cart, then proceed to checkout.
4) Your cart is emptied!
This problem only happens in Firefox. In Chrome and IE, the cart is not emptied.
The only way (so far) I could resolve the problem was to either:
a) Use default WP permalink, or
b) Uncheck "Clear cart when logging out"
Can anyone reproduce this problem?