The vast majority of the processing will be within the VPS. However, each time a certain event occurs, data will need to be passed to a database on a dedicated server. This data is under strict privacy regulations and therefore needs to be secure. Is this possible using your service, and what is the best way to go about it?
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…
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?
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.