In addition to creating VMs based on captured templates, please allow to stop / deallocate and start / allocate existing VMs on demand (for some background info see e.g. [1]). That way an Azure VM would not be billed unless it's being used as a Jenkins node.

One thing that might be tricky is to handle the case where a reallocated VMs get assigned another IP because to Jenkins, it must still appear as the same node.

[1] http://blogs.technet.com/b/keithmayer/archive/2013/06/19/windows-azure-virtual-machines-there-s-more-than-1-way-to-shutdown-a-vm.aspx