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.