UPDATE: We finally discovered a solution to this issue, which was simpler than we would have expected. Here is the process to get your flows connected properly after refreshing a Business Central environment:
1. In the refreshed environment in Business Central, open the "Workflows" page. Delete all of the Power Automate workflows that are present (they will have been copied over from the environment you refreshed from). If you cannot delete them due to active workflow instances, disable and rename them.
2. Open the "Manage Power Automate Flows" page. Update to the correct environment by selecting Configuration > Select Environment
3. After changing the environment, you should see your existing Power Automate flows that you need to re-link to this refreshed environment
4. For each flow, disable the flow, then enable it again. This action generates entries in the Workflow table and the Webhook Subscriptions table in Business Central, which is what you need for Business Central to recognize it properly.
Your existing flows should now be properly connected to your refreshed Business Central environment!
Cheers,
Craig