The latest version of Jenkins appears to have updated agent / label management in a way that prevents the vSphere Cloud Plugin from setting labels on created agents. Agents are created, run, and become ready – but jobs are never started because labels are not set. 

Downgrading to Jenkins 2.420 immediately resolves the issue. 

Was not able to find any logs regarding trouble getting labels, but please let me know if there is something specific I can search for. I will update if I find anything.

What's new in 2.421 (2023-08-29)

• Optimize performance of label parsing. (pull 8395)