We figured out the problem -- there was a subflow added to the flow, that had <storeOutputAutomatically>true<storeOutputAutomatically>. Prior to yesterday, the only elements that had the <storeOutputAutomatically> tag were record creates, record lookups and 'show toast' actions. We fixed the problem by checking the 'Manually assign ...
This configurations could be changed using Metadata API, not native apex, so 1 and 2 answer is no.
You can use metadata API to deploy those action override for Account
You can get dependency on any custom object using MetadataComponentDependency tooling API. But, this is still in beta version (MetadataComponentDependency).
You should probably not be deleting and recreating Connected Apps as a general rule. You only need once instance of it, and it need only live in your production/business org. As long as you have the client Id and client secret, you can use that app for any org you wish to connect to.