The IP your VPN uses must be from a pool of known VPN providers, which are generally known and easy to block. Another options that the service scans the data packets for VPN fingerprints.
I suggest looking for a small virtual private server and loop traffic through it using a free server VPN installation. A simple VPS capable of this could cost you $10 a month if not less. If you're already paying for VPN access, this may actually be cheaper.
Some disadvantages that come to mind with this approach:
- Your VPS IP is probably quite static, so if you're worried about people tracing the connection to your location then this may not be the best solution.
- Will not hide your activities. If you do something illegal (e.g. break copyrights, publish questionable content, etc.), your activities can be traced to your VPS instance and your VPS provider can and most probably will give your information to the authorities.
- Requires technical know-how unless you can get someone to set it up for you.
- Will most probably not protect against packet sniffing techniques unless you know how to scramble the data you send.
VPN is not that resource intensive from what I've heard, so you could run something else on the VPS too if you want to. A website, Mumble, and so on. More bang for your buck!
Another option is to find another lesser known provider which has not got its IPs blocked yet.
Bottom-line: using known VPN providers might result in IP-pool blocking. using your own VPS for VPN connectivity will mitigate this, unless the service does packet inspection.