I'm not using Windows as a server - I'm using xrdp on Linux to access remote X sessions, since it's MUCH faster than any alternative (nomachine, vnc, etc.)
A VPN is pretty trivial on Linux too, running OpenVPN is just a matter of installing it, writing a simple config file (5-6 lines) and running the command.
I've set up a VPN connections between my Nexus and a VPS in less than 30m (I use OpenVPN for Android instead of the official client since the latter doesn't seem to support pre-shared keys).
