Solved! Go to Solution.
Just had this issue, I think was caused by the user of one of the connections being deleted - or the connection ownership being updated.
Anyway you'll know this is an issue if the Flow isn't listed under Apps -> Details -> Flows.
I fixed this by exporting the flow, importing as a brand new flow (renamed) and then adding the Flow in as a new Flow to the App (Actions -> Power Automate -> Create new Flow). You can then simply manually amend the code to use the new flow without your code being deleted.
What an absolute crock of sh*t everything to do with Power Platform ALM is. Microsoft should be ashamed of themselves pushing this half-baked cr*p on us.