The only solution I found to resolve this issue was to change the integration account to a different Azure region. For example, using "Spain Central" always resulted in this error. However, creating a new integration account in "North Europe" worked immediately.

Additionally, make sure that the Logic App is also located in the same Azure region as the integration account. If they are in different regions, this can cause issues as well.

It seems there might be some limitations or inconsistencies depending on the region. This should be documented by Microsoft to prevent users from wasting time testing multiple scenarios just to find a working one.