A shot in the dark:
Is it a multi process app? Or, did you at any point switch from multi-process to a single process? If so, the app may have hit a (new) bug, similar to this one: can't deploy to multiple regions anymore - #9 by catflydotio
In the past when our app was bit by a similar issue (a year or so ago) which was also using the tricky-to-tame autoscale setup, only creating a new app with both those traits (autoscale and multi-process) removed fixed it for us, then.
You can also see if setting --max-per-region has any effect (1, 2) when deployed with rolling strat.
Or, unstick the deployment with fly vm stop and friends: "vXXX is being deployed" freeze - #3 by kurt