Obviously locality makes it a lot easier but even then, there had to be a point where you had 5 users and nobody else. How do you get past that?
First, I posted the site on a local subreddit, which got us up to about 20 users. We started telling friends and friends-of-friends, and my partner ponied up about $800 to run some radio ads. Fun fact: radio stations will whip up an ad for you as part of their fee. It was pretty fun hearing that on the radio.
After that first hundred users or so, we started sending press releases out to anyone we thought might care. This was much easier being local, and easier still because my wife is a writer with some experience being on the receiving end of PR press releases, and she wrote it up for us.
We were lucky enough to be featured in the local paper of note, got an interview on local radio, and a week later we were up to about 1000 users. The rest we've picked up more or less organically through word-of-mouth and/or google.
Edit: This was back in October. I wrote this mostly about the technical details, but it has some experiential stuff too: http://adambard.com/blog/my-experiences-deploying-a-small-cl...
Pre-registrations for online dating are different than with other kind of consumer apps. Daters eventually stop being single. So pre-registrations are most useful if they are for a short period of time - no more than, say, eight weeks. This ensures that your profiles are accurate (single people are actually single and will become active users once you launch.)
You can see it at http://www.ladieschoicevictoria.com/
It's been very interesting so far. We've had a strong positive response from two groups of women: young women who have had bad experiences with more open dating sites, and older women who, speaking generally, aren't totally comfortable with online dating and prefer the privacy of having a profile only visible to people you select. We've got a similar ratio to "Check Him Out", about 60% women, and about 1600 users overall.
We haven't made any effort to monetize yet, but it seems clear that the relative success we have had (including being covered in a local paper) is thanks to both the privacy features and the local aspects.
I don't think we've solved the problem, but I do say that the experiment suggests to me that some combination of safe and local is the essential ingredient that the author is looking for.