Here is my take on the level scaling:
I want places that I can't walk into at level 1 and expect to live. If I am exploring the deepest, darkest mine in the world at level 1, I want a Balrog to eat me, not goblins to slaughter. Of course, this mine should not be something you randomly wander into at level 1 either. Conversely, If I go into the sylvan forest outside of the starting town at level 20, I should laugh at the little puny wolves, not run in fear from the storm giants.
Part of what makes this work is level appropriate loot, for the monsters/dungeon. Sure, a level 20 can wade through the rats in the sewer no problem, but there is nothing there worth his time. On the other hand, tackling the dungeon thats fairly challenging will net you better loot, making it worth the effort.
Coupled with this is how you get quests. Basically, the higher level you are, the more prestigious people who will try to give you quests. At low levels, you operate off of the beggar's rumors, at high levels you get summons from the king. The various levels of people will have knowledge of different types of challenges. The beggar knows about the rats in the sewer, while the king is concerned about the dragon raiding villages.
As for the people who say that it discourages exploration to have above-level dungeons, that is a very odd stance to take. "Oh, I'm a level 1 character, but I really want to go and tackle the hell world now. Why should I need to be powerful before entering hell?" If you don't have any relative progression, why bother having a leveling system at all? Just make everything a mostly stable power, and you can go wherever you want without a problem? Why bother with the whole charade of leveling, but not increasing, or sometimes decreasing, in relative power? If you are leveling up, then it should mean something. Gaining access to new areas is one of the most satisfying achievements for me in a game. I have now made progress, I have a new area to explore, and my boundaries have expanded. This occurs in all sorts of well-known and popular games: Zelda, Pokemon, Metroid...
This can also be designed for improved replay much more than the level scaling would. If there are 10 level 6 dungeons and 2 dungeons is enough for me to level to 7, I will not be exploring 8 of the dungeons on this play-through, since I have moved past them. Or I could be tackling dungeons that are a bit harder or easier, depending on my preference. Next time I play through the game, I can explore a different set of dungeons, and still be exploring, instead of running to my favorite dungeon.
This is not to say there can't be places where level scaling is used. If you have a rival, they can be level-scaled appropriately. Or an Arena-challenge, like oblivion had after you finished the normal tournaments. There can also be directed battles where someone is attacked you because of your power level. You don't get directed battles that are too weak, because they wouldn't think they could take you, or too strong, because then you are not worth their time. Some possible directed battles include bounty hunters, bandits, assassins, etc.
There should also be dungeons above the level of the main plotline (like the unkown dungeon in pokemon) to provide a further challenge to those who want it.
I feel a game structure like this would work out very well. You have a clear progression of power, rewards for taking on harder dungeons, lots of replay value, lots of freedom of exploration, clear accomplishments and benefits of leveling, no issues with underpowering yourself from leveling, no issue with the level 1 fish one-shotting you, no enemies leveling past your combat cap, a clear sense of becoming more powerful in relation to the world, and the ability to maintain a consistent level of challenge.