I now have another client reporting these same random issues. Their site hasn't been updated at all in several months. The site uses the same type of checkout so I can only assume something has changed at PayPal. It might be something minor that affects only certain types of transactions but I can't reproduce it yet.
I noticed another user reported a similar issue. Not the same checkout but similar enough that I wanted to check to see if he found a solution. http://www.webassist.com/forums/posts.php?id=44811
Thanks for any thoughts you might add.