I followed the route of cheap VPS/Amazon/Rackspace Cloud and I found out the hard way that my android ICS tablet did not work with L2TP/IPSEC PSK vpns. You didn't mention if you were using Linux, Android, IOS or Win 7. PPTP/GRE VPNs worked great however, as did port forwarding SSH. You could also use a squid proxy on those setups, but that just makes it more complicated.

me: USA | Team: Not-in-USA | Thus: much time spend on phone/video every day