You should take a look at the URL's that you are using with the checkout. Make sure that they are consistent in how you reference the page, especially the redirect pages for PayPal. If you are not sending them back to the same domain that they came from the session could be lost and the cart emptied.
So if you are on thesite.com then the links for the return page should all start with thesite.com/. If you are using www in your site reference then the redirect URL must also have this www in it like this:
www.thesite.com/
If this is the issue you should also be able to reproduce it yourself by trying different variations of the domain when you begin shopping. If you are getting a number of users that are not able to complete the transaction then there must be something to it, we just need to figure out under what circumstances this is happening in order to come up with a solution.
