CDS (Dataverse) Error — UnresolvableHostName. The provided host name could not be resolved.

We started getting the above with two of our flows (which were part of our managed solution). The provided host name was actually something like org12345.crm.dynamics.com, which clearly indicates that this is a host on Microsoft’s end. We noticed that this error occurred in when the first action of the flow is called, which retrieves a record from the Common Data Service (Dataverse). When we attempted to re-submit the flows, we kept continued having the same error.

As weird as it sounds, the solution to re-process both flows was the following:
1. Open the flow, and save it.
2. Re-submit.

Kudos to my colleague Dennis Carriere for suggesting this.

Note: This created an unmanaged layer for both flows in our managed solution. We will need to delete these the next time it is time to upgrade our solution. Also, we have a ticket open with Microsoft Support to get a better understanding of what exactly happened here.