I am experiencing this problem now and I am using Opensourcehost, which is a ZC certified host. I contacted them and am awaiting a response.
Aside from the "Your Shopping Cart is Empty" screen after adding a product to the cart, I see that my error log is loaded up with entries stating "File does not exist:" on each page that anyone visits. However, these pages are visible and they do load when I go to view them. Tracking log indicates visitors are seeing the pages as well.
I had set globals off in .htaccess a while ago and things had been working. The problem just arose today for some reason.