Ask HN: What's the best way to get users for a PAID web service?

I saw in another thread where people were discussing the best way to go from 1 to 1,000,000 users. A lot of suggestions were presented, and even more so on Quora. Some of the highlights include making it exclusive, rewarding users for inviting others, etc.

It seems like a lot of these great ideas are focused on free services where the challenge is to get people in, not so much to convince them to pull their wallet out. Since there are possibly a whole different set of challenges for paid services, what would be some great ways to get more users specifically for services where the customers would have to pay? Are there methods of acquisition that would be completely different from the free ones?