As for the IP Restrictions, the gateway through which all incoming requests are processed is the same for both the Request Connector and the HTTP WebHook Connector. While you may be using the action here, there is a WebHook Trigger that works in a similar fashion but as a trigger instead.
As for why you are getting failures at times would depend on how requests are being routed from your APIs to Logic Apps. One way to ensure access just from a single IP is to route these callbacks to APIM and let APIM forward the request to your Logic Apps. This way, all requests to your Logic Apps would be coming from APIM.
To route the callback requests through APIM, you will need a special API/Operation in APIM that will forward requests to the URL passed in the header or a query parameter.
So instead of directly calling the callback URL, you will call this APIM endpoint with the callback URL in a custom header or as a query parameter. The APIM policy for this operation will use the set-backend-service and rewrite-uri policies to forward this call to the logic apps endpoint.
The callback-url itself is generated by the webhook control of the logic app. How could I introduce an APIM in-between?
As alternative - how can I re-set the access control limitation on Logic Apps to allow any IP? To give more insight, the Logic Apps are trigerred by recurrence (so no external http endpoint is triggering its start). It is just that it contains a webhook element and it used to work with the IP restrictions... until recently. Is it safe to allow any IP and how can I do that - I mean how does the arm template look for 'Any IP' case?
Updated my answer to elaborate on how to setup the APIM operation to achieve this. Its usually best to restrict IPs to prevent abuse but I suppose you could change it for your case since there isn't a trigger to abuse. In the ARM Template, just an empty
accessControl: {}should do.