Conectar varias tiendas entre si

Hola, me gustaria explicaros un trabajo que tengo encargado.
El caso es que tengo un cliente que tiene varias tiendas, repartidas en varios pueblos, no muy lejanos.
Hasta ahora cada tienda tenia su propio programa para el control de stock, almacén, etc. y me ha propuesto cambiar el programa que usa en todas sus tiendas para centralizarlo desde su tienda principal. O sea que desde todas las tiendas accedan a la tienda principal para utilizar el programa y asi poder controlar mejor sus stocks, almacén...
Me gustaria que me ayudarais a escoger el tipo conexiones que tengo que usar para conectar las tiendas y más o menos la configuración del servidor.

Mi idea es la siguiente, todos los consejos son bien recibidos:

Poner un Servidor en la tienda principal donde se instalará un Windows 2003 Server, donde se conectaran todos los usuarios a través de Terminal Server y seguramente crearé un dominio para dar permisos a los usuarios. También se instalara el programa de la tienda, que ya tienen escogido.

En cada tienda tienen unos 5 PC's, son 4 tiendas a parte de la principal y tienen su propia red local. La mayoria tienen Windows XP Pro.

Para poderse conectar al servidor utilizaré el Escritorio Remoto sobre una VPN entre cada una de las tiendas y el servidor de la tienda principal.
La VPN aun no lo tengo claro como hacerlo, si por software o hardware.
Por software creo que seria un poco engorroso, cada PC tendria que conectarse a la VPN y después al terminal server. Y el servidor configurarse para enrutamiento y acceso remoto.
Y tambien veo complicado configurar el programa con las impresoras locales de cada tienda, ya que cada PC remoto tiene que conectarse con la VPN para poderse ver sus recursos compartidos.
Me han recomendado que utilize hardware, que cada tienda tenga un router Firewall / VPN que se conecte al router VPN de la tienda principal y asi cree una red entre todas las tiendas.
Aqui ya no se que marca utilizar, ni los precios que pueden tener.

Bueno esto es a grosso modo lo que quiero hacer, me gustaria vuestra opinión al respecto, muchas gracias.