The first thing that will need to be done to access what is going wrong is to reproduce the issue. Without first being able to reproduce the issue it will be extremely difficult to determine what may be wrong.
Based on what you are reporting it would seem that this is only occurring for non registered users, is that correct?
If so you should only be running tests without logging in or registering. If the cart is empty this indicates that the session has been cleared or that maybe the user got stopped when going to PayPal.
Do you know if the users experiencing this issue are trying to checkout with one method versus the other? This will help to pinpoint what the problem may be.
