If Machines (VMs) were created with flyctl m run ... then flyctl deploy ... won’t work (why?). Instead exec flyctl m update --image registry.fly.io/<image>:<tag> ... (ref, docs) once per VM.
flyctl m run ...
flyctl deploy ...
flyctl m update --image registry.fly.io/<image>:<tag> ...