Это вполне стандартная ситуация. Например на ряде контор что я обслуживанию именно такая же. Я использую оспф и стоимости маршрутов, а туннели поднимаю через всех провайдеров. Ну с динамическими айпи конечно дднс.
По поводу оповещения, можно использовать на головном офисе скрипт пингующий все ваши клиенты определенным колвом байтов, например 1000. Клиенты исходя из прилетающих ицмп запросов помещаю айпишники в определенный адрес лист. Дальше только ваша фантазия:)