When you destroy a volume, it’s actually soft-deleted first; that gives us a little time to recover the data if the volume was destroyed by mistake. Volumes waiting to be fully destroyed are in the pending_destroy state that you saw.
What changed is that flyctl switched to using the Machines API to work with volumes, and the new Machines API endpoints include pending_destroy volumes. Because of a bug, flyctl didn’t filter these out and tried to use them like any other volume during deployments. Sorry that you ran into this! The bug was fixed in v0.1.78, released on Monday (August 14).
(v0.1.78 also restores the old behavior of fly volumes list: you won’t see pending_destroy volumes there anymore. You can still find them by using the Machines API directly.)