The game mechanics that make a game "Nintendo Hard" were often transported from arcade games that required the player to spend more money to keep playing after his character was killed. Except that when they got ported over to the console, there was no coin slot, leaving you stuck with a fixed number of lives and highly limited or non-existent continues.
The concept has recently been satirized on the Internet, most famously by The Angry Video Game Nerd, who pointed out that via Sturgeon's Law, most examples of Nintendo Hard games are often a result of sloppy or bad design.
A lot of these examples are simply rookie mistakes. For a company, establishing an identity and building the fanbase takes priority over finding the proper challenge level. Often the designers will go for something highly distinctive, take a lot of time designing and making it look right, and not spend enough time on the actual gameplay and level mechanics, then realize too late that they've (completely unintentionally) made a monster. Ghosts 'n Goblins is a good example of this.
A factor that has often been considered to be into play on whether or not the game is actually Nintendo Hard is how huge the development staff behind it was. Many programmers tell that when you are programming a game alone, you usually get pretty good at the game's own mechanics, so much in fact that the difficulty level of your game gets adapted towards your high level of skill. When you are building a game with other people, the entire staff needs to understand the basic mechanics of the game and it is better not to scare them off with high difficulties when you want them to work together with you. This may also be a reason why many NES games were hard, as the creative teams that made them were significantly smaller than those in the current industry.