You can get a low-end VPS for even less if you look at some VPS companies special offers, like $15/year for 1GB RAM, 20GB disk, 1TB transfer/month. Yes, low-end and most likely overbooked servers, but still decent enough for a proxy.
You don't need so much RAM for a VPN sever with a few users. You can get by with 128MB (or even less if you're ruthless), and get such servers for $7.50-$15.00 per year.
