Hello,
Glad to hear you were able to find the cause of the problem in your PayPal account. To address your request to have us deliver orders before payments are confirmed that is something you have the ability to change if you are willing to take the risk.
If you go to Seller Admin > Edit Payment Preferences you can uncheck the box which reads "Wait for pending payments" and then our system will deliver orders as soon as we get notice of a pending payment as opposed to a completed payment.
I'm not sure if that would have made a difference in this specific case, but it does send immediate deliveries for people who pay via e-check, for example.