I've had tremendous success using Remote Desktop - I'm guessing your firewall/router needs to forward port 3389 (the RDP port). Terminal Services in a multi-user environment is also superb.
I should note there are weaknesses with VNC security, so you should always tunnel it like using SSH. Personally I like Remote Desktop/Terminal Services.
There is a good freeware (for the Community Edition) VPN program called SSL Explorer you should take a look at:
http://www.3sp.com/showSslExplorerCommunity.do
Addendum: As another look-see, OpenVPN is another choice you can examine. It takes a lot of configuration and detail, but it is open-source (if you are an open-source junkie).
http://openvpn.net