It does seem that the issues arise for both registered and unregistered users. We had an unregistered user receive the 'empty cart' message but also had a registered user try to process through paypal and they did not receive any confirmation or failure notice.
It is very difficult for me to test either circumstance as the process works to pay through both paypal and direct credit card when I test it?! We haven't had any successful paypal direct payments made for the life of the store, but when we contact paypal they test the site and say that it is working.
All of our successful transactions are direct credit card and from registered users.