I think you're looking for Datagram Transport Layer Security. It's essentially SSL/TLS but slightly modified so that it will work over UDP. This is roughly the same thing that OpenVPN uses for its encryption, except that OpenVPN predates DTLS, so the implementation details are probably a somewhat different, but not dramatically so.
Luckily newer releases of products like OpenSSL already support DTLS, so the hard work has been done for you.
Once again, I've managed to tinker through the problem (but not for too long as the original question and this answer supposes it to be :). I've been through almost a month researching the solution for the problem, and I'll leave it documented here just in case anyone happens to bump at the same problem.
Actually, the loopback interface is really what I knew it to be: an address assigned to a dummy, always up interface on a machine. The connectivity problem between the remote GRE router and my router was due to another problem: GRE keep-alive packets.
It turned out that the remote Cisco router was actually sending me odd GRE-encapsulated packets through the tunnel. These packets encapsulated another GRE packet, and these, on the other hand, carried a protocol number of zero. A quick browse indicated that these packets are GRE keep-alive packets, which are send periodically (in my case, every 10 seconds almost exactly) and, if properly deencapsulated and rerouted by the peer, should be echoed back to the sender, since the innermost destination address contained the sender's source address.
The fact is that the Linux kernel did not properly feed the deencapsulated keep-alive packet again into the routing chain. If it did, the packet would be rerouted back to the sender without further complications. Instead, it delivered the packet to userspace, so that it was possible to write a simple program that listened to such packets in raw mode, and echoed them back to the sender. Running this program and echoing back a couple of packets to the Cisco router, the GRE tunnel went 'up' on the remote side, the PIM routers exchanged hellos and I finally could listen to the multicast traffic that I expected to listen to.
I've learned a lot from this experience, specially the part that, when messing with obscure protocols (or, at least, obscure protocol features), you can't simply count at all on peer-knowledge. No single network analyst on the remote side could help me in any aspect in this regard, probably because this behavior was undocumented.
Best Answer
I'd expect gzip in ssh and stunnel to be faster than lzo in openvpn, but..
Given that your bandwidth is so precious, I'd recommend you test your particular application and your particular data against ssh, openvpn and stunnel.
ssh, stunnel and openvpn all have support for compression. If your data is highly compressible, you may be able to trade CPU time in order to save some bandwidth, but this assumes you have sufficient CPU resources available at both ends.
On some systems, ssh makes it easier to configure strong, mutual authentication than stunnel and openvpn.
However, stunnel and openvpn might be much easier to run unattended and reliably (monitoring, reconnects, etc) which may influence your decision as well.
Finally, there's always the option of moving as much data as you can when nothing else is using your network, or make use of bandwidth throttling, if your environment allows it.