The "Provision Paid Pending Services" automation tasks runs every 5 minutes by default to provision paid pending services. A paid pending service is considered paid if any linked invoices are paid. If there are no linked invoices, it's considered paid.
During order, the service is created first, then the invoice. If there is a delay between service and invoice creation, and the automation task runs between this delay, a service may be provisioned though it has not been paid since the invoice was not yet created.
I'm not sure what the right solution is here. Ideally, I suppose, it'd be great if there were some kind of "lock" put on a service that is released once the invoice has been generated, and then the automation task ignores services that are locked. Or, a delay in provisioning paid pending services to allow sufficient time for an invoice to be generated, though that is arbitrary.
A good solution to this would be to have the entire process of the service + invoice creation be in a database transaction. The problem, however, is that there already exists transactions that occur in parts of the process when adding/updating services and when adding invoices, and since you can't have nested database transactions, we would have to refactor the process. I already had plans to refactor models in CORE-2430, which is where this could be resolved.
How often does this occur? An order has to be placed at exactly the right time such that between when the service is created and the invoice is created the cron happens to run the provision paid pending services task to fetch those services. While possible, that race condition seems like a shot in the dark, and I'm sure there would be other race conditions with similar undesired effects.
We could delay the provision paid pending services task as you suggested by some arbitrary amount of time, and that may reduce the frequency tremendously, although it will still be possible to encounter the issue. That would probably be alright in the interim.