The most creative puzzles i have seen in a long time was in Sam&Max s3, where you had to use max's psychic abilities, like seeing into the future, reading someones mind or changing into some object etc.
What made them fun was that it never quite gave you the result you was hoping for, like when you had to bet on which special move Skunkabe would use in a fight, using the ability to look into the future wouldn't directly tell which ability he used, but you would get enough information to deduce it.
In The Tomb of Sammun-Mak they had divided the game into 4 film reels (chapters), and whenever you got stuck on one reel you had to switch to another to find the information you needed to solve the puzzle you got stuck on.
Strictly speaking this is not really a single puzzle, but more of a change in the flow of the game, i however still think it put a nice spin to the puzzle solving.
I could also mention the time travels in the first Diskworld game, which is not so different from the film reels in Sam&Max.
And I was also quite fond of the way you had to use Spot's ability to change form in The Wispered World.
To answer your first question, then i would define a creative puzzles as something that has to be solved in an entirely new way, rather then just be a variation on some old theme, and would force the players to actually think about it how to solve it.
If we take your example with hacking into a computer, then neither of the options you give is really anything i would thing of as creative, as long as the password is in a book I have found, then i don't really care how I have to enter it. (I'm trying really hard to come up with a creative example of how to hack the computer, but aperantly i lack the imaginitation
).
One more thing, which is perhaps slightly off topic:
I would really like to see more dialog based puzzles, like in Culpa Innata or L.A. Noire, though not necessarily in the exact same way as in these two games.
And finaly to answer the second question you started with:
Yes we definitly need more "creative thinking" in puzzles, there are simply too much of the same old puzzles.
The good thing is that there seems to be a lot of never games, where the developers at least have tried to be creative when designing the puzzles.
