I’m having the exact same issue, with two different apps, one of them:
Searching for image 'registry.fly.io/reference-structuring--staging:main-57ae53e185c798bc7cd98db6b9fed8f926ebbc78' remotely...
Error failed to fetch an image or build from source: Could not find image "registry.fly.io/reference-structuring--staging:main-57ae53e185c798bc7cd98db6b9fed8f926ebbc78"