What is the best solution for this network routing scenario?

CodeBlox

We have a vendor who provides a specific service for our organization. It depends on our routing passing certain traffic to their router which traverses our firewall. Lately, recent events have called for the desire of redundancy in our alternate location across the country. Currently, we have default routes for internet traffic at both sites and could do the same for this specific traffic. Thing is, I am trying to think of the best way to handle the routing for this to work where either route could be used for any branch at any time. It would need to work out in such a way that if a branch (which is a unique subnet) is not reachable through side a, the vendor should be able to route that traffic at side b. It would be about 60 routes. I was thinking we could have the vendor make use of IPSLA however, that would require many many (60) IPSLA operations and track statements. I am not sure if that's common or a best practice. Any ideas? I have thought this through and it seems to me that they would need to learn our routes but that just seems weird to do through the firewall.