1) SEO is harder today than it was in, say, 2000, just like the App Store is more competitive than it was at launch. That is a long way from non-viable, though. There are recent, high profile, successful startups like Mint or OKCupid where SEO was a core traffic acquisition strategy. (OK, you will not be as good at SEO as OKCupid, but you can be as good at SEO as Mint is. They're in an uber-competitive market and found a spin on it such that the skeeziness in the space worked in their favor, because most people in consumer finance are trying to sell you a credit card and Mint was trying to save you money by, ahem, selling you a credit card.)
2) Links >>>> everything else, with regards to ranking for head keywords. Happily, startups are in a great position to get links. BCC has a couple of hundred in five years -- a YC startup can pick up a couple of hundred by launching. AirBNB practically has a hundred from PR coverage in the NYT. A single well-executed link bait or viral sensation seeded with your hundreds of linkerati friends can really, really move the needle.
3) You can still dominate large portions the tail of the keyword distribution through superior execution on your content strategy. Is this the tactic for all seasons? No, if you're just doing brand arbitrage against the same 400 New York hotels that every other person with a phonebook has access to, this will not lead to dethroning established competitors. If, on the other hand, you're finding unconquered frontier and settling it, you win by default. Can I give yet another plug for services which do not target twenty-something white and Asian males and, instead, which target the need of underserved demographics? If your primary competition is Demand Media you should ROFLstomp them for most of the keywords you actively target. (And learn from their model for scaling content creation up.)
As to why they have that ranking? Well, they do linkbait so well that almost isn't fair to call it linkbait any more. They also do other things. One particular tactic which used to be quite popular in dating is viral quizzes.
They have toned down the aggressiveness of that tactic in recent years, probably after a different site got torched for it. (Plus you don't have to be quite so aggressive after you've already won -- then you can use self-reinforcing authority and translate your commanding market position into, e.g., a competitive moat like their blog posts.)
They also execute very, very well. For example, it's easy to say "Viral apps win" and it is hard to be Zynga. Similarly, it is easy to say "Get more links and you'll win" and it's hard to top OKCupid's execution on that -- most individual tactics I've seen them try have execution in the top 1%. They're #1 with a bullet at linkbait. Those quizzes are better than 99% of quizzes. Their use of the product to support the SEO is better than 99% of startups. (Humming a few bars: OKCupid has rabid fans amongst folks whose dating behavior results in banhammers at other dating sites, and they leverage that to the hilt.)
Sponsored #1: Match.com
Sponsored #2: top10bestdatingsites.co.uk
Sponsored #3: matchaffinity.com
Ranked #1: plentyoffish.com
Ranked #2: dating.guardian.co.uk
Ranked #3: eharmony.co.uk
Ranked #4: mysinglefriend.com
Ranked #5: loopylove.com
Ranked #6: flirtbox.com
I can't locate okcupid in the first 5 pages (at that point they were all no name sites) this seems strange to me, is ok cupid #1 for you?
Guess they rank differently based on geographic location...?