I was pondering the puzzle platformer thing earlier for a wiki entry I was writing (http://en.wikipedia.org/wiki/Platform_games). I came to the same conclusion as you that Penguin Land is the earliest clear cut case of a puzzle platformer.
No, not at all. It's a platform game where the predominant challenge is from solving puzzles. Toki Dori, Wario Land 2/3, and Lost Vikings are all good examples, along with the handheld DK games like NeoZ said.

