Azure Service Bus team helped us to identify and fix the issue.
Posted Nov 23, 2017 - 11:06 PST
Investigating
Customers may notice that some builds may start with significant delays somewhere between 5 and 10 minutes. We believe the cause of that is issues with Azure Service Bus queue used by AppVeyor backend workers. We are still investigating and working with Azure support. Thank you for your patience.