Today on ci.jenkins.io: R. Tyler Croy updated the plugin, and after a restart, the queue filled and no agents were provisioned.
Jenkins log showed tons of messages like these:
Jun 07, 2017 4:01:06 PM com.microsoft.azure.vmagent.AzureVMCloud canProvision
INFO: AzureVMCloud: canProvision: template ubuntu-jenkinsinfra is awaiting verification or has failed verification
Jun 07, 2017 4:01:06 PM com.microsoft.azure.vmagent.AzureVMCloudVerificationTask registerTemplateHelper
INFO: AzureVMCloudVerificationTask: registerTemplateHelper: Registering template ubuntu-jenkinsinfra on AzureVMAgents-... for verification
Clicking 'Verify Template' in Jenkins system configuration wasn't enough, one apparently just had to save the system config form without changing anything (???). Then the on disk template definitions (thanks to Job Config History plugin) switched from <templateVerified>false</templateVerified> to <templateVerified>true</templateVerified> (plus a few other changes, but this one seems relevant).
Then, provisioning worked again.
This seems like not great behavior.