Online vendors don't accept pre-paid Visa? This is news to me. How do they even know - it's just a regular Visa card. I've used a number of such online (mostly ones I got in all kinds of promotions) and never had a problem - I didn't even think anybody could do that and I doubt Visa would allow you to do that - to reject pre-paid Visa card. Do you have any source to this claim?
While Paypal will accept it if you provide a Visa-verified billing address, not all will, and that would defeat the point of anonymity anyway.
Visa and AmEx also forbid international payments on prepaid cards, and most merchants nowadays require a verified billing address. (This wasn't the case as recently as 2009).
Remember that a prepaid card is not a credit card - there's no risk of you not paying, because they [Visa] already have your money and yet merchants refuse to take it. It's completely ridiculous.
This sounds more like a problem with the issuing banks. Is there any way for a merchant to know that a card is prepaid? If not, how would they know not to check the billing address?
(Semi-related: Do prepaid cards count as debit for purposes of the regulation on swipe fees?)