To be clear, generally if the Internet goes down in Dallas, at least the Dallas office will be offline whether your server is in "the cloud" or not. (VPN relies on Internet)
The short answer is setting up a VPN connection to any external server is relatively straightforward if you are already technically familiar with some details of networking and server config. Amazon Web Services even has a concept called "Virtual Private Cloud" (http://aws.amazon.com/vpc/) which gets you a server environment with VPN access baked in. Most other hosting companies might make it a little more difficult to set one up because of the hoops you'll need to work through to get networking set up right.
We have several AWS servers that we use OpenVPN with, as well as a couple (ve) servers from MediaTemple.
Perhaps as a side note (but related to solving uptime issues), "the cloud" you refer to with Linode is not actually a "cloud." It's just a single virtual instance that they are giving you, probably one of many instances on a single physical 'host'. If the virtual instance goes down, or the host server goes down, or the physical network connection to the host server gets severed, you still face the same downtime issues that you would with a normal server. Granted that is significantly less risky than hosting in your own office (generally), but bear that in mind.
In my humble opinion (and I emphasize the "humble," because this is more of a perception of mine), a real "cloud" should really be composed of a cluster-like environment with CDN, redundancy, backup, and failover capabilities from multiple locations, thereby reducing (as much as possible) the risk of downtime. Obviously even in this environment there will be single points of failure, but again - it's all about reducing risk.