It all depends on how you define "puzzle", of course. However, I find that "code writing puzzles", as you term them, tell me far more about the candidate's ideas and approaches to solving problems than abstract discussion. Even relatively simple problems (like the hash-table example from the OP) often have enough edge cases and follow-up topics (cache locality is a particular favorite of mine) to give you insight into what the person is thinking about when they solve a problem. You say that you don't want to see code, but instead "see into his/her brain." But how do you do that without looking at code? One thing I've found out when I was interviewing for my replacement at my last job is that people are very, very good at bullshitting. Asking them to actually write code strips away the bullshit and forces them to actually show you what they're thinking. Sure, prior work is great if its available, but I know of many really good programmers who don't code all that much in their free time, either due to family commitments or because they have gasp have interests other than programming.

I accept that when you're programming "for real", you have reference books, Google, StackOverflow and all sorts of other resources to help you out, and I accounted for that. I wasn't picky about syntax. I let them use whatever programming language they were most comfortable with (as long as it wasn't something terribly obscure, like Brainfuck or J) I even accepted the occassional algorithmic error (e.g. greater-than/less-than being flipped around) if it was clear that the applicant knew what they were talking about and was quick to fix the error once it was pointed out to them. But I still insisted on some code. I would be willing to bet that the programmers who you are referring to -- the ones surrounded with reference books -- would be more than able to bang out something like a quicksort or a binary tree without references. Sure, it might not be a perfect, production-ready implementation, but I'd expect something that at least resembles the correct algorithm, along with a discussion of the tradeoffs and edge conditions.

Frankly, I think memorization is, if anything, underrated in computer science. Our access to knowledge is quite similar to the memory hierarchy in a computer. Working memory is like RAM. Long term memory is like disk. Books and references are like the network. Having algorithms and data structures memorized is like having a local cached copy of a network resource. It allows you to be faster and more fluent when you're programming because you're not context switching constantly as you look things up. And just like in sports or martial arts, it doesn't matter what advanced techniques you know if you don't have solid fundamentals. Basic algorithms and data structures are the fundamentals of programming. When I ask a candidate to demonstrate their knowledge of such by writing code on a whiteboard, I'm assessing how good their fundamentals are. The rest can be taught.

EDIT: And of course, I forgot the most important fundamental of all: Big-O notation. Knowing algorithms is useless if you don't have solid basis for determining how and why one algorithm is better than another.