Database Tunneling

You can create a secure (encrypted) tunnel (via SSH or a VPN of some kind) to the dedicated server, which would go over the net (unfortunately consuming bandwidth).

If you want maximal performance, locate the dedicated server in the same datacenter as the Linode; for example, Linodes' Dallas operations are in ThePlanet's datacenter, who also sell dedicated servers.

SSH is the easiest to use, but not the most performant; you'll likely get better performance out of OpenVPN or some other non-TCP-based solution.

I'm not sure what sort of requirements you could have that would rule out a properly secured VPS, though…

In short, the requirements involve HIPPA and integration with our shipping department. Can't go into too much more details than that.

As for the tunneling, is IPSec tunneling allowed? That is what is currently set up on our dedicated server, and an additional tunnel can be set up as well. Can that be set up on Linode as well?

Absolutely. As long as packets leaving your Linode originate from one of the IP addresses assigned to it (which they will in this case), IPsec VPN will work.

In the future, if you'd like to add additional Linodes to the VPN, you could tunnel between the Linodes on the private network (within the same datacenter) and not incur any bandwidth charges.