This sounds like a job for IPSEC to me.
IPSEC is "baked in" to modern Linux distributions. It's completely transparent to the application layer and "just works". I'd go that route for intra-machine communication that needs to remain private.
A "host to host" IPSEC configuration with pre-shared keys is pretty straightforward. In CentOS, for example, there's already a method to configure these host-to-host connections as part of the normal "network-scripts" functionality (see http://www.centos.org/docs/4/4.5/Security_Guide/s1-ipsec-host2host.html).
Depending on the distribution of Linux you're using, it may be very easy to configure, or you may have to do a bit of work. You won't need any VPN startup / shutdown scripts, tunnel monitoring scripts, etc-- it'll all "just work" at layer 3. That, to me, sounds like a winning solution.
I use OpenVPN frequently and heavily, so I'm not "dissing" on OpenVPN here, but as a solution to your particular problem, I think it's sub-optimal for the following reasons (in order of my degree of concern):
It creates a parallel network infrastructure. You'll have to be sure that your intra-host communication uses the right destination IP addresses such that communications travel across the VPN, rather than the public IP network. This could be particularly fun if you plan to use DNS names, since you'll need to do something to your DNS (either creating hostA-secure, hostB-secure, etc host names, or creating a DNS "view" that always returns the "secure" IP addresses when the queries come from the "secure" hosts) to be sure that you resolve names to the "secure" VPN IPs.
OpenVPN is point-to-point. You'll need to configure a mesh of OpenVPN tunnels or route the OpenVPN traffic "hub and spoke" through a single host. IPSEC is totally peer-to-peer, and you can easily configure a mesh topology with IPSEC and dynamic keying. With pre-shared keying it's a bit more work, but you can configure a mesh topology that way, too.
OpenVPN is a userland program that will need to be started up. That's not a huge deal, but IPSEC lives in kernel-space and "just works" w/o starting any userland programs once it is configured.
I don't get why people think that IPSEC is so hatefully difficult to configure. IPSEC with pre-shared keys is as easy to configure on modern distros as OpenVPN with static keys (if not moreso-- typically your distro handles starting/stopping it automatically). IPSEC with dynamic keying, using a PKI, requires almost the very same steps as configuring OpenVPN with certificate-based authentication.
The complexity of OpenVPN creating a parallel network topology with a second set of IP addresses would be the killer for me. I'd want my hosts to be able to talk using the same IP addresses that they receive unsecured communication with, "automagically" encrypting the connections between each other transparently.
For what the poster described, I think IPSEC sounds like the best solution (for the reasons I described above). If the poster were talking about interoperating with other operating systems, and not just looking to secure the communication between some hosts, I'd recommend OpenVPN specifically.
I would agree that interoperating the various Linux IPSEC implementations with anything else is difficult (as is interoperating nearly any IPSEC with nearly any other IPSEC implmentation, actually). I've managed to get Cisco PIX to OpenSWAN tunnels working, and I've had some success with statically-keyed tunnels coming from Windows machines. I've never even touched any Juniper gear, so I can't speak to it at all.
I've used OpenSWAN (when it was FreeSWAN, actually) and I'd agree that the docs are difficult. Since RedHat "chose" the KAME tools to manage the Linux 2.6 kernel IPSEC stack I've stopped followng OpenSWAN. For the very few times that I've needed host-to-host IPSEC in the last few years (on RHEL or CentOS-- all I really work with in the Linux world), the KAME tools have done fine. I've been using the "official" documentation from RHEL and the documentation from the KAME project site with success.