You can use a local service provider and set up a VPN (Virtual private network), basically a private voice/data network that makes use of the public (shared) WAN infrastructure, rather than a dedicated private facility. The whole client setup side takes approx 30 minutes including testing. I managed to strike a deal with my local ISP within 1 day and they setup the connection from there end the same day and supplied me with the relevant usernames and passwords.
Costs for the call are unbelievably cheap and this goes for accessing your email etc from wherever you are in the world, one of the main reasons for adopting a VPN approach.
The level of security provided by a VPN is high using advanced encryption and authentication protocols that protect data from unauthorised access.
Should your users require greater security for document transfers and emails then they could always use an approved PGP protection. I managed to route all traffic through the company's Firewall. The only problem, which was minimal, that I ever encountered was that connection speed can vary at different times of the day depending how many users were actually accessing the ISP at the time. Of course. I was only using a standard 56k internal modem in my remote users laptops and workstations, you can always opt for a faster type of connection, ie ISDN frame relay ,ATM etc
hope this helps you in your first steps.