This seems perilously close to a shopping question, which are prohibited on SF (and other SE sites, apparently) by the FAQ. You also fail to mention what OS will be running on the cloud servers; but I'll go ahead and assume it's Linux.
That said, my first preference would be for IPSec, since it's built into Linux, it's incredibly robust, and well-integrated at the network level (so you don't have to mess with routing tables). There won't be any issues about authentication, since it's all done with pre-shared keys or certificates. It integrates well with iptables firewalls. It recovers well after extended network outages. It comes up automatically at boot time via standard /etc/rcN.d scripts. With IPSec tunnels in place, applications need only throw packets at IP addresses; the encryption all happens way down the stack from there.
Failing that, OpenVPN. It's more complex than IPSec, but shares many of the same advantages.
Failing that, ssh tunnels if you must - but you'll be forever running around putting them back once network outages have made them fall over. I'd rather have (yet more) root canal work than do this with ssh tunnels.
