I have thought about running Terminal Services or Remote Desktop Service but that would be my last option since it's costly.
Since the actual machines aren't doing any processing, you can use cheaper desktops or thin clients. You have 3 main options.
1) Go with a Terminal Server (Self-hosted)
2) Go with a hosting provider for AC
3) Go with a VPS/Cloud Provider
4) See below
VPN's are typically not feasible due to Internet limitations. However, if the offices are not too far apart/obstructed, there's something called Wireless bridging where you bridge the network between offices. This is not a new technology but recently has become very affordable. You can actually get full gigabit wireless links with offices as far as 200KM away. The upside is you don't have to pay a provider for the link between offices.
.png "ACUF Donor I")
