I just watch a walk-though of one of the hardest NES game I ever played It was called Legacy of the Wizard. The game is like a huge maze. I put so many hours in that game, but was never even able to find the first boss. Here's a link to the first video of the walk-though.
Here is the map for the game. You can see why It is so hard to find out where to go.
