It was PIA - PrivateInternetAccess. I first tried ExpressVPN and for privacy I'd recommend ExpressVPN because they located in a place with no data retention laws. However PIA has port forwarding support and that is crucial for my case.

Both support payment via Bitpay. ExpressVPN returned the money no problem after I've discovered that they don't do port forwarding.

I'm sure there are many more, but Mullvad is one VPN provider accepting bitcoin payments (as well as cash).