hi
can you revert back on the kinda ip addressing being used by your SP ? static or dynamic assignment ?
afaik if you have all your locations being dynamically assigned then its bit difficult to bring them on the VPN connectivity.
if they are having static ip address on their wan port you can have point to point ipsec tunnels configured between them to have vpn connectivity.
regds