Насамперед, визначте для чого потрібен Вам VPN. Якщо йдеться про шифрування, то стандартом є IPSEC. Для Linux э дві реалізації:
http://www.openswan.org/ або
http://www.strongswan.org/. Це обидва клони FreeSWAN-у, тому в основних підходах подібні. Для FreeBSD стандартом є racoon.
Якщо Вам не йдеться про криптування, але лише про маршрутизацію приватних мереж через публічні, можливо вистачить лише GRE. В ідеалі GRE over IPSEC -- вирішення усіх проблем (і захист і маршрутизація). Додатково про способи тунелювання тут:
http://lartc.org/Щодо потужностей -- ніяких надмірних ресурсів не потрібно. Якщо звісно йдеться про "традиційні" канали 64-128К. Врахуйте, що є "межа доцільності" криптування. Скажімо 25 каналів по 10Мбіт криптувати буде дорого.
Усю VPN спокйно можна будувати і підтримувати на Лінуксі. Я розгортав і підтримував подібну мережу, все працює на "ура". Крім того реалізації IPSEC сумісні між собою і можна сміливо будувати, наприклад, Лінукс-Cisco.
І ще, для рішення Linux-WinXP/Win2k/Win2003 _дуже_ гарно використати l2tpd over IPSEC. Про це тут:
http://www.jacco2.dds.nl/networking/freeswan-l2tp.html. Там детально і покрово описано, як будувати тунель. А потім ви можете "запхати" настройки в Windows RAS і все підніматиметься автоматично. Працює гарно і без проблем + в тому ж RAS-і можна налаштувати і резервні лінки і інші нюанси маршрутизації.