From my limited anecdotes of the time, I believe Google actually did it. We're not talking about programming-related brain teasers here, we're talking about non-programming ones.
e.g., "3 light bulbs in a room" and "family crossing the bridge" being the classic examples.
You have a bridge that can only take a certain amount of weight at once without collapsing. It's dark at night and you have only one flashlight. A flashlight is required to cross the bridge, which is traversable in both directions.
You have a family of people of varying weights (the exact numbers you'd have to look up) - determine the optimal way for the family to make it across the bridge.
Thanks. I don't think that's a bad one. In fact, like the Towers of Hanoi, I think it has enough parallels with computer science and engineering to be a good interview question.
Can you be specific with some examples? As demonstrated elsewhere in the thread, some people perceive the same questions as appropriate and others perceive them as "brain teasers".
e.g., "3 light bulbs in a room" and "family crossing the bridge" being the classic examples.