When given a label to the job (for example, machinegroup1) and a node matching that label is online but busy, Jenkins will very often not bring a node online to perform this job, instead saying "Waiting for next available executor" and waiting in the queue until the other job is done (sometimes days). If there is no online machine that matches the label, it brings one online properly.

I watched the logs and it gets as far as attempting to map the job to a possible set of executors, then repeatedly fails until it determines that none are suitable candidates.

Our nodes are launched on-demand, offline when not in use.