The best coding challenge for a hiring process I ever had happened, of all places, when I applied for a PHP development position at Fender.
At the time, their marketing department did all of their web development in-house. I don't recall all the specifics; there was a round table meeting between the manager of the unit, the team lead, and one of the senior developers. At the end of it, they sat me in the cubicle area with their other developers, gave me an MBP with MAMP on it, and a piece of paper outlining what they wanted me to code - a simple CRUD app. It didn't have to have any fancy styling, but it had to look ok, and it had to work. It was "open book" otherwise; use google or whatever other resource as you needed it. Also, all this happened while the other devs were in the area; it was basically a time slot from 2:30pm to closing time...
I'm thinking - really? Something this basic...
But given what you had to do - essentially from a blank slate, including the database, set up the tables, build the SQL, code the PHP, integrate the form to talk to the PHP "backend" and update things, refresh and show the updates, etc...
...well, isn't that basically what most software dev work is, at the core? And if you can't do any of that...
Of course I got the position, and worked there for a couple of years; not the easiest environment I've ever been in, but certainly very interesting.
During it, though, I got to experience, from the "other side" what I went through - and I was amazed and dismayed to see how many people were interviewed who couldn't do it. Who had what seemed like great resumes who couldn't even start. Who'd sit there for 2+ hours, and not type a thing. Who didn't even google up something, or ask a question, or...
We had one guy sit for a while, then just got up and walked out without a word.
As I read comments like yours, and others elsewhere, I can see that this is more common than not. You are right to believe that there will be those that will "memorize" fizzbuzz, which I why I think a challenge similar to what Fender asked for is a better test. I know that some developers would balk at it, but I think the time invested may be worth it, to show you are able to do the job, and can come up with your own solution to a problem, and not just some regurgitated answer.
Interesting aside:
A colleague of mine I had worked with prior, unknown to me, applied for the same position at Fender and was given the same laptop as I did. But they had forgotten to wipe it! He saw my code, and didn't know if he was supposed to expand on it or what; he told them "hey, this looks like my friend's code...?" - and they realized what they forgot. They thanked him for his honesty, wiped it, and continued on with the process. He also ended up getting the position as well.