But they are likely to provide IP addresses used to connect to your server. So now you're facing the same problem, if you wanted to hide your IP address.

Are they so likely? Do you mean they keep logs of every attempted connection to every vps? Even in countries like Netherlands? I'd bet that's less likely than keeping a log of their paying customers' names

>allows you to pay with bitcoin, making it more difficult to trace you

...but they require a valid credit card/paypal deposit beforehand, which kills the whole point.

I had no idea of that requirement, kills the whole point indeed :(

edit: there's a list of providers allowing only bitcoin as payment method: http://cryto.net/~joepie91/bitcoinvps.html

With referral link?

Why shouldn't I?