Hi @Gareth T
I'm glad that you were able to resolve your issue and thank you for posting your solution so that others experiencing the same thing can easily reference this! Since the Microsoft Q&A community has a policy that the question author cannot accept their own answer, they can only accept answers by others, I'll repost your solution in case you'd like to Accept the answer.
You have a logic app that posts to an internal web service. The app started to experience connectivity issues. You verified the gateway and VNET configuration had not changed.
You determined that the issue was related to Border Gateway Protocol (BGP) routing issue.