The failure is actually in setting/world building.
If you solely focus on the power levels at hand and have the power and abilities of encounter solely scale with levels, you´re creating that problem.
This can be countered by integrating high-level stuff and threads early on in the game, foreshadowing events that could happen.
Three examples could be:
- While a very low-level party does overland travel, they witness a great old red dragon devastate an village a bit further along the road. All they can do is help the survivors.
- While in a major town, a full blown demon incursion starts and they see other high-level characters spring into action, battling a balor while they handle some lemures.
- Rumors and Gossip. Just tell small stories of things that happen in another place or another time.
I agree with Codwyn here. Just having encounters matched to the party's level is kind of jarring.
For the DM, they should plan as what the "big threats" are have them work toward their plans of world domination / destruction / etc, pretty much as the beginning of the campaign. A well-written adventure path takes a lot of this work out for the DM so they can see who the real mover and shakers are at the end of the campaign path and then reasonably think as to what they are doing when the PC's are at 1st level. So when the players are adventuring from 1st to 18th level and ready to take on your ultimate villains, then along the way of the campaign, the PC's should have seen or experience some of the big threat's handiwork and machinations.
Another approach is the inherent nature of the campaign world itself as being balanced by both forces of powerful evil and powerful good. Take the Forgotten Realms for instance. We know that in 3.x, it was just filled to the bring with high-level and epic-level threats. So how come they didn't just try to bowl the world over? They are, but they are being opposed constantly by equally powerful and epic-level good guys. This is the inherent design (for good or ill) that the players can buy-in on suspending their belief. When it's the PC's turn in the campaign world, it will involve the one threat that saw an "opening" and is moving forward with a plan and the PC's the only ones at the time able to stop it.
Other campaign worlds has the bad guys pretty much already won. Ravenloft, Obsidian Twilight, Midnight are all campaign settings. Evil creating more evil is now the status quo and the PC's role in the world is survival or finding some way to put a cork in all of it.
Also, a problem with high-level believability rests that we don't see how literature treats it very often. Most of the fantasy literature that we read involves characters who just get by, are luckly to have their
longsword +1 and fight things like ogres as their really tough opponents. We have FR novels and some Dragonlance novels that give a higher-level treatment, but that's about it. What are other novels? I'm a big fan of the Wheel of Time series. There are a lot of high-level stuff that goes on the novels the pretty much the whole series starts out with yokels from the farmlands becoming kings and powerful mages to defeat a great evil. But what was the great evil doing in all that time? Well, the great evil is in prison, but his super tough followers are very busy in the whole campaign. They start wars, they engage in petty schemes to one-up each other, and they spend most of their time working behind agents instead of exposing themselves. There's a valid reason to work in the shadows instead of exposing themselves. If they did, they would likely be attacked by the other evil baddies and / or opposed by a powerful group of mages called Aes Sedai.
So when I plan a campaign, I do think as to who the major villain is from the outset, their most powerful minions and then work out what the plan is and what they need to do. As the players progress through the campaign, they will see those works or plans come into fruition. They will be able to stop a few of them in which the minions will take notice and then have to switch to putting-out-fires mode.