[djcapelis]

I actually think OkCupid does a decent job on most metrics. Their matching algorithm is simplistic, but adaptable and dynamic. It's globally available with almost every interaction with other people on the site and the extensive profile information usually results in decent keyword search. Frustratingly they don't allow you to search by specific personality traits they detect, but sorting by match score actually tends to yield more relevant results than sorting by other fields.

I would agree that most dating sites suck, but surprisingly it turns out one of the free ones is pretty decent. (Being free helps deal with the limited corpus issue nicely as well.)

I think they solves the high-dimensional space issues by lazily evaluating match scores and caching. I have no idea what they're doing on the backend, but I'd guess they don't actually calculate scores for all n^2 matches everytime someone answers new questions.

The computer science behind the site is frankly fascinating. While the site itself doesn't take itself seriously, they seem to take the algorithms driving it very seriously.

The bottom line is it's worked for me. I'm not someone who can't talk to people in person, I'm just someone who's busy and found it more efficient to meet people online. For me what exists now is actually workable, not limiting and efficient.

I'm sure it could be improved, but the two problems you cite haven't been that problematic in my experience.