VPN redundancy on NAS with two ISPs

I have a third party service that connects via a VPN (tunnel is one of the Amazon variety, I did not set it up).

I have two sites, each site has two separate ISP connections. There is a tunnel that connects my two sites together, and each site has two tunnels connecting to the 3rd party service for redundancy.

The problem is that the two tunnels at each site to the 3rd party route through only one of the interfaces, so if that ISP goes down the tunnel goes down with it. The 3rd party does not want to create four new tunnels (two tunnels at each site) and suggested that I get a "fronting" IP at each site, use that as the endpoint that their tunnels see, then if my primary ISP goes down they won't have to change the endpoint on my side of the tunnel.

I understand the concept of what they are describing, but how is such a thing accomplished? Where would I even get IPs that aren't locked into one ISP or the other?