Also, is this a recent requirement to deploy an agent with a label because the flows would always be deployed with a label and an agent without label, would never pick it?

I don’t think this is a recent requirement. Local agent adds a default label though, so flows registered with the default label work out of the box.