So your links are something like (sorry on my screen the ascii graph looks good but this seems to kinda squash it together):
| <- VPN tunnel
/ | \
/ | \
Site1 Site2 Site(x)
You are being requested to provide a redundant access solution to the downstream sites? Shouldn’t WAN disaster recovery already be part of the customer’s network design? Is this a service that your organization typically does for hosted AD or Exchange customers? You mention the sites use metro ethernet to get back to the HQ. So are the sites in a close geographic area? Maybe they could use microwave or some other wireless backup links between locations.
I don’t want to make light of the needs of the customer and what you want to do for them. Your organization is in the business of hosting services and applications. It sounds like your company needs an arm that designs network access services or use a partner who specializes in network services (like a Virtela). This would enhance your organization’s offerings and provide some level of comfort to your customers that they are getting a strong value-add to the services they get from your company.
Some questions to consider also:
1. What is the purpose of the downstream sites coming back to HQ for access to the hosted services? Does the HQ monitor this or is there some other security concern?
2. Would there be much incremental cost (both to you and the customer) to have a VPN tunnel to your hosting center? This would take out the reliance on the links to the HQ site. The issue with this would be though keeping up with the number of VPN links for this customer.
I hope this helps you through your thought process and gives you some ideas on how to proceed. Good luck.