>They explicitly refuse to accept prepaid cards even though they are VISA/MasterCard (BTW the same problem with Google Compute)... or am I doing something wrong?
Prepaid cards can be purchased anonymously. If you were running a cloud provider, would you rent a server to somebody who was essentially untraceable?