IME if you can't control both ends of a VPN then don't expect much success. IPSEC appeared to be a god send for solving these problems - but by the time it got implemented where were just too many different ways to configure it - even if you get your implementations from the same source.
Although there are relatively cheap off-the-shelf units which are straightforward to implement in a planned network - this approach does not scale down to SOHO installations where the internet connection may be via a modem which requires client software/non ethernet connection to the client device or a router which implements masquerading.
Have you tried using openvpn? Software will run on every flavour of Unix/Linux/POSIX including MacOSX and Microsoft NT based kernels, uses SSL so easily crosses NAT.
(note: SSL tunneling does have additional overheads which you don't have with IPSEC, however I've previously run VOIP over SSL based VPN - before openVPN was as mature as it is now - and had no detectable problems with jitter / frame loss, bandwidth overhead was relatively low too. I've not run OpenVPN over such a large network but given the same underlying technologies I wouldn't expect any issues)