Sherm noticed the same people were being affected and PayPal provided some logs showing how we were replying to their Instant Payment Notifications. Together, the two items exactly pinpointed the problem. It was my fault. Blame me.
The problem only affected people that paid without using a credit card, such as people paying using their existing PayPal balances.
If you've posted a support request about a lost payment, give Sherm a couple days... he'll get to it. I'm also going to write a quick script to find all the payments that came in but were never setup by searching through our PayPal email reciepts.
Sorry about all this.