For those who need it, I've just set up a VPN that's peer-to-peer and works for all games that support direct connections (not using a remote server), and it should even work when you are behind two layers of NAT or other unfriendly firewalls. It works a lot like Hamachi and uses the 25.0.0.0/8 address space. It's free and fun, and doesn't require you do anything once it's set up. Follow these instructions to use it.
Update: thanks to Chris we have some nice, step-by-step directions (downloads a text file), which are probably more approachable to new Windows users. Below are my original instructions, which you should probably still read, but Chris's instructions will get you up and running.
WARNING WARNING WARNING WARNING WARNING: pay attention to the following as it's very important, before you even get started.
1. There is no security. Anyone who can read this forum thread can join. You can't rely on this VPN for anything sensitive. Not that I'd expect otherwise, and it's good practice to just assume the whole world is out to get you all the time, but remember that this is a public network and anybody can see anybody else. You should imagine that you have a public IP address, for all the good that does, and act accordingly. Do not host or transmit stuff on here that you'll regret. Most operating systems nowadays are robust on public networks, and do include firewalls. And of course you should be keeping your software up-to-date, and only expose services you need, and password-protect all important shares or resources. You should already be doing all this stuff, of course, but here's a reminder to be careful.
2. Although I've tested it independently and found it to work from my Windows VM, please follow directions carefully and bear in mind that things might fail for odd reasons. There is an easy bailout no matter what, and I don't imagine anything tragic will happen, but understand you are ultimately on your own here. Of course, feel free to ask for help if you need it.
And now, the instructions:
1. Get the latest stable version of Tinc for Windows. We assume you are on Windows because that's where all the games are, but if you need help with another OS do let me know. The server in fact runs Linux.
2. Run the installer. Install everything, except that you may, if you wish, uncheck the tap adaptor driver for the platform you do not use (if you are 32-bit, you could uncheck 64-bit, for instance, or vice-versa).
3. Install the tap driver for your platform. In the tinc program folder, find the tap-win32 or tap-win64 directory, and run the addtap.bat file. You need to have elevated privileges. If you're successful, a message will appear in your console, followed by a prompt to press a key to continue. Press enter to exit the console window.
4. Find the tap device, and rename it to "gamers", exactly as shown and without the quotes, obviously. You must find the network object and rename it. How you do this depends on your OS, but I'm fairly confident I don't know the procedure for anything later than XP as M$ are determined to make it as stupidly hard as possible. But I believe newer versions of Windows now call this something like "Network and Sharing Centre", and there's an option to "Change Adapter Settings". And indeed, here's a wonderful guide, which also incidentally talks about the different types of exposure I was warning you about earlier. Read and understand it, please.
5. Next, grab this file, and unzip it. Copy the contents into your tinc program folder. Specifically, the tinc.conf file must be in the same place as the tincd.exe file, and the hosts directory should be a subdirectory of your tinc folder.
6. Open tinc.conf with notepad or another text editor. Change the second line, as directed by the first, and save it. Specifically, replace the name with a unique name for you. It doesn't matter what, as long as it has just letters and numbers and _ characters.
7. Next, open an elevated command prompt, and switch to the tinc directory. As in
cd c:\program files\tinc
(or whatever is appropriate).
Now, generate your keypair, by typing this and then pressing enter:
tincd --generate-keys
It should be safe for you to press enter twice more, to select the default locations. If you did step 6 right, you'll notice that the proposed file in your hosts directory, for the second prompt, now matches the name you have picked, and the private key and public key files should appear in your tinc and tinc\hosts directories, respectively.
8. Finally, it's crash test time! Still in your command prompt, type this, to start the client and register it is a Windows service for future restarts:
tincd --bypass-security
If you did everything right, your network adaptor list should show you that you have a 25.0.0.0/8 address. You can try to ping the DHCP server by typing this into a command prompt:
ping 25.0.0.1
If you receive replies, you are connected!
Now simply play your games, and instead of worrying about port forwarding and all that, simply hand out the address you have been assigned.
Any questions, just follow up here. And sorry it's such an annoyingly advanced procedure. It would be easier if the software was designed for client-server authentication, but it was really meant for mutual setups where both sides were under the user's control. If I can figure out a way to make it easier, I will, but this should get us going.
Enjoy!
Further notes.
1. Port forwarding and firewalls. It would be helpful if you could forward and/or unblock TCP and UDP port 655 to your machine from the outside. It is not mandatory, but it will certainly decrease connection setup time, whether from you to another person, or another person to you, and it will also help the network in case somebody is not so lucky as you. I cannot explain how to port forward because it's different for each router, but try portforward.com for many routers. Also, you need to manage any host firewall software you have on your computer. If you use the stock Windows firewall, add tincd.exe to the exceptions list, or a port exception for both TCP and UDP ports 655. Moreover, the Windows host firewall will, in the default posture, which is typical for public network profiles that are not otherwise configured, be very strict in preventing access or discovery, so you might have to wrestle with it in order to see incoming packets from the VPN interface or offer discoverable services.
If you don't have access to your router's configuration interface, you can try to use UPnP. It is not attempted for you automatically. However, if UPnP is available, Windows should show it to you as an "Internet Connection" in your network connections list. Get properties, and there's an interface to add port mappings in this way for the tinc ports (TCP/UDP ports 655).
2. Starting and stopping. You can use the services control panel to start and stop tinc, if required.
3. Uninstallation. Use the deltapall.bat file to remove all instances of the tap driver from your system. Next, in an elevated command prompt, type these two commands:
cd c:\program files\tinc
tincd --kill
That removes the Windows service. You can now uninstall tinc with the Control Panel, and delete the tinc directory.
4. IPv6. IPv6 is supported. Peers that have IPv6 communicate directly with one another, but incur higher latency communicating with IPv4-only peers. On the other hand, communicating only using IPv4 will disadvantage constrained IPv4 peers, whose only direct connectivity is IPv6 or, in the worst instance, peers without IPv4 connectivity at all, whose only connectivity is IPv6. It is up to you to choose who should suffer more, and it is undoubtedly true that IPv4 is still the more ubiquitous protocol at the moment, but I'm for the future. If you disagree, change the "address" line in the "Mintaka" file in the hosts directory to use the IP address 173.203.201.199 directly, instead of the hostname "mintaka.sabahattin-gucukoglu.com".
5. Virtual machines. Run this setup in the virtual machine guest, and not on the host system, unless you know very well otherwise and understand advanced routing. Ideally, your guest virtual machine should be bridged to your LAN, but this is not absolutely necessary, if you don't have the option.
Edits: various clarifications, mostly to make things completely unambiguous. IPv6 notes. Clarify that firewalls and/or NATs should be opened up to TCP/UDP 655 where possible, and explain the role of Windows Firewall in handling the VPN interface. Notes on virtual machines. Link Chris's instructions at the top of the post for people who need it. Update Windows download link to 1.0.33 (from 1.0.31).