Postfix

Veo una solución factible a tu problema con el postfix, no es la única que se puede aplicar, pero esta es la que yo probaría. Visto que la sede principal si puede enviar correos al exterior podemos configurar en cada una de las sedes especificando como relayhost el servidor de la sede central, por lo que todos los mail se los enviaran a la sede central que este a su vez enviara los correos. En el servidor de correo de la sede central configuramos una trasnsport_map para que según que dominio de cada una de las sedes se dirija el correo a un servidor u otro, tienes la "Guía rápida de Postfix"[1] en la que encontraras los detalles de configuración explicados con claridad, Cuéntame luego que tal te ha ido ([email protected]).
[1] http://www.kleenux.org/articulos/guia-postfix/guia_postfix.html