La mayoría de los servicios usan https para manejar información sensible, por lo que utilices vpn o no, nadie se entera de nada, porque la información es cifrada de punto a punto. Si mandas información sin cifrar sobre un túnel cifrado, entonces al final del túnel la información se puede apreciar sin cifrado.
Yo pago 7 dolares al mes por usar
PIA (si compras el paquete del año te sale a la mitad por mes) y he tenido muy pocos problemas con el. No guardan logs (al menos no por más de 10 minutos? o algo así).
El único problema (y con cualquier servicio que haga de intermediario) es que compartes una IP para cualquiera que este usando este servicio. Y muchos sitios guardan información relevante a tu IP. Por ejemplo, me encontraba canciones que otras personas escuchaban cada vez que entraba a grooveshark.