I had this error for almost an hour but found a solution resulting into a big worrying dilemma. The solution let to realization that one cannot run gcloud app deploy while there is a task in the task queue to be served by the server version to be replaced.
The error was: ERROR: (gcloud.app.deploy) Error Response: [9] Cloud build XXXXXXXXXXXX status: FAILURE that xxxx part is some auto-generated base64 value.
The solution was: Deleting all the tasks in the task queue
Question: Is there workaround or I have to delete all the tasks in the task queue (like I did) before deploying?
Details: Server is written in nodejs.
I suspect that the need for emptying the task queues when tasks destined for the version being deleted could be driven by the virtual "head-of-the-line blocking" that would occur in this case, affecting other services/versions in the project (task queues are shared across a project) and maybe even the related GAE infra functionality.
Fundamentally re-writing a certain app/service version kinda defeats the whole purpose of versioning (imagine git allowing you to change the content of the commit/refpoint associated with a certain SHA signature!). But in some cases - for example when the version is actually used to implement a certain execution environment - that's intentional.
What you described is not the only issue with GAE deployments over-writing a certain version of an app/service (which I didn't think about before, BTW, thank you for that!). Another one is captured in Continuous integration/deployment/delivery on Google App Engine, too risky?.
If your deployments with version re-write are actually an attempt to implement deployment environments you may want to also look at a couple of other potential (IMHO better) alternatives compared in Advantages of implementing CI/CD environments at GAE project/app level vs service/module level?