I'm not a fan of puzzle interviews at all either, and I agree that they're usually not very relevant except as a sort of specialized intelligence test which may or may not really be indicative of job performance. That said, working with the interviewer on something neither of you have solved does sound more enjoyable, interesting, and informative for both of us than having the interviewer sit behind a facade of perfect technical knowledge. At least that way you'd get to experience some sort of teamwork with the person, whom you'd presumably be working with.
I've heard of places having a candidate sit down and do some pair programming with one of the developers. That seems like a similar approach which emphasizes concrete development and coding over algorithms or puzzles.
I mean, what puzzles can I give a recuiter to test things relevant to me?