According to Lyle, it is possible for an order to be completed regardless of when the payment is received. In other words, the payment could be received first, and THEN the order completed ("Checkout completed"). However in our live site experience, this is not the case. That's why I created a different Workflow-ng configuration to not act based on when Checkout is completed, but rather, when a Payment is entered for an order.

paulg, you can use devonl's step-by-step tutorial, but here is my Workflow configuration that fixed our Paypal issues.

Invoked on event: A payment gets entered for an order
Condition: check the order balance (less than or equal to 0.00)
Action: Update the status to completed

I'm not sure if this is related to the order of events taking place, but it was the only solution I found that worked for orders coming in from PayPal. As I've explained ad nauseum, PayPal orders don't always come in at the same time a user completes checkout. This might mean that a user "Completed checkout" in the sense that, they purchased items, their account was created, etc. - but PayPal might be experiencing delays, which it oftentimes does, and so the order will remain in Pending until the payment is received - and the balance becomes 0. Sometimes this doesn't happen for minutes, hours - even days.