Secure video chat program as an alternative to Skype

Why not use Windows Live Messenger video chat? Or if you want to go really techy and secury you can install your own SIP proxy and with the above mentioned VPN and a variety of SIP clients you can make your own platform, so to speak.

I can't really give advice on a video chat program. But concerning security, all you have to do is setup a VPN (IPSec or otherwise) so that either your girlfriend can join your local network or vice-versa. This will give you a secure encrypted channel from point to point. Then, you just have to find a Point To Point video chat program that does is truly point to point. (as in, never contacts the internet if not needed)

WLM isn't the best option anymore - not since MS decided to make it an 'ad serving platform', but the best (or only I think) option for Open source is Jabber, otherwise known as the XMPP protocol. Which is a secure, encrypted protocol BTW.

You can run a chat server yourself, and secure that. No need to run on Google's Gtalk network (which is XMPP) or others. There's a load of server and client software on the XMPP website.

If you access Gmail using https (which is the default setting now) and use their video chat software, then the connection to Google's servers will be encrypted, which would secure you against any sniffing on an unencrypted WiFi network, etc. Google would have access to the data, but I don't think they keep logs of video chats, just text chats. It's supported on Windows, OS X and Linux, and is very easy to install. I've been using it lately, and it seems to work quite well.