OK, no idea how I managed to overlook this one: Hamachi is a VPN application that can set up direct connections between computers, even if they are behind firewalls and NATs etc. The difference with other set ups is that it only uses a third party server to bootstrap the connection, but the connection itself is direct and doesn't flow through this third party in any way!
I remembered reading about ways to do this a long time ago. I think it was some Microsoft knowledgebase article, but I cannot find it right now. Anyway, I've been hoping for something like this for while.
Oh! There is also a Mac OS X graphical client next to the official commandline one. Clients for Linux and Windows are also available.
Give this a go!