I haven't seen that. We use paypal for our store and haven't had an issue like that.
I'm wondering if it has something to do with the way your checkout code is structured. If you want to attach your checkout code to a reply I can see if something stands out. Otherwise the best thing to do is to try to figure out what the failures have in common. It is really hard to track and fix a problem you can't reproduce, but once you can reproduce it I'm sure I can help you get it fixed.
You may want to create a debug table in your database and start dumping information about each sale. Insert the session id and date and time as well as the entire contents of the session and post and then when the next failure happens you can take a look and see if you can spot an anomaly or similarity. The first step to fixing any problem is understanding the cause. Something has to be causing it.
