Assumptions: D&D; sandbox; a significant number of competent adventurers exist, and have existed for a long time.
How can this seeming paradox be best resolved, assuming one definitely wants to keep the sandbox element?
A beautiful question, and I'll endeavor to answer it.
1) Treasure is not actually easy to retrieve. I cut my teeth on Gygaxian adventures where treasure was almost always hidden, obscure, or bulky and in those cases where it was not it well guarded by traps and creatures. A good test of whether you are doing it right IMO is whether at the end of the adventure the dungeon would still be worth exploring by a lower level party. It's very rare for players to find all the treasure in my games, and as such another party could come along in a few years or a few decades and explore the dungeon and also recover treasure. There are almost always secret doors the party didn't find, flagstones that the party didn't overturn, secret compartments that didn't go found, piles of trash that weren't thoroughly searched, and treasure that was looked at but its real significance wasn't understood.
2) Dungeons have histories. Another naturalistic explanation for the dungeon is that it is not static. Dungeons may be partially cleaned out every few decades, only to have new inhabitants move in over time and bring with them their own treasures. Treasure then accumulates from banditry and failed expeditions until some new party comes along and takes the good and obvious stuff. But just as higher level PC parties don't always scoop up all the copper or silver and less worthwhile treasures, higher level NPC parties might have better things to do than worry about hauling every scrap of treasure out of the dungeon. As such, it could very well be the case that lower level PC parties are entering the dungeon in the wake of a higher level PC party that killed the worst stuff and took the best stuff, but very much left interesting things for a lower level party to face. It's perfectly reasonable to have signs of exploration in a well known dungeon.
3) Most dungeons are not well known and rumors of treasure are actually fairly rare. One problem with typical dungeons that breaks suspension of disbelief is that often in published scenarios or games a typical plot hook will be essentially a giant flashing neon sign saying, "Treasure to be found this way.", and every drunk the bar knows the legend of the lost treasure of Zulsadoom which happens to be two rooms into a dungeon guarded by two orcs. If in fact the location of treasure is well known and its guarded only by things that people with average demographics (certainly NPCs in the town given their stat blocks) could in fact recover, then it is reasonable that it all got recovered decades or centuries ago. A simple solution is for the PC's to be among the first that discovered whatever clues that lead to a dungeon that has been lost a very long time, perhaps even passing out of memory of the local inhabitants. You can do that in various ways - a town drunk accidently discovers the dungeon in the course of his affairs and reports it, a natural phenomenon like a flood or earthquake reveals a previously hidden entrance, some children discover the entrance exploring an area and one or more go missing, a monster is awakened in some fashion and begins stalking or haunting the area, or the PC's discover a map or other clue pointing to the existence of a dungeon in the course of a prior adventure.
4) Any dungeon which is both well known and famous is utterly lethal. It's ok to have a famous dungeon that is well known provided the level of characters required to successfully traverse it is much higher than is common for your demographics, so that the overwhelming majority of NPCs that attempt it die, leading to the place being avoided by reputation except by fools. In my game, NPCs tend to be levels 1-4, with leaders that are levels 5-6. Most NPCs have rather average ability scores and a focus on non-combat skills, so even if there are a few 6th level characters in the town that are very competent at what they do, what they do is usually not go down into dark and dreadful places and kill monsters. Rare and exceptional NPC's are levels 9-10, but they tend to be older individuals suffering from the effects of aging with below average physical ability scores and no longer vigorous enough to be adventuring. Adventuring parties that exceed these demographic norms (like potentially the PCs) are usually these legendary heroes that are the most powerful characters the area has seen in a century or more, and even then they certainly do not clean out EVERY legendary dungeon in the area. So any dungeon that requires 10th level or higher characters to survive it is pretty much unexplorable and it's reasonable that the PC's might be the first group in centuries to attempt such a heroic deed that also had any reasonable chance of success.
5) Adventurers aren't that common. If you have anything resembling the horde of Smaug the Golden, you have to have Smaug guarding it and a shortage of legendary heroes in these parts. Your demographics have holes in them if it is profitable for the PCs to go exploring, but there are NPCs near by that could have more easily done the same exploration and reaped the same reward. In my own game, 'adventurer' isn't even common enough to be a recognized career. When NPCs hear the word 'adventurer', what enters into their mind isn't the image of a heroic wanderer doing deeds of errantry but rather a wealthy and frivolous tourist. The word 'adventurer' in the setting doesn't conjure to mind facing off against monsters, but a jaded noble looking for exciting new foods, exotic cultures, and fantastic but not necessarily dangerous sites. This in the average persons mind is considered to be close enough to looking for trouble to be insane anyway. If the PC's describe what they actually do, the first words that probably come to mind are 'mercenary' and 'sellsword'. These are fairly common in the setting, but most of them are paid to fight each other and vanishingly few are the sort of multicultural broadly skilled characters that specialize in exploring mystic and darkened lairs the way the PCs do. There are lots of things about the PC's that immediately strike NPC's in my setting as weird, including the fact that people of different professions and even different races are companions, that the PC's are extremely young to have acquired such deadly skills (particularly in magic), and that the PC's seem weirdly fated and destined for greatness. Wise NPCs recognize in this the machinations' of the gods, and try to stay out of the way. In short, a company of mercenaries that looks like the PCs small elite company with very diverse skills is not something that happens all the time in the setting, nor could you necessarily collect a bunch of NPC's from an area to replace the PCs. Additionally any reasonably detailed sandbox has enough adventure hooks in it that even after the PC's retire you could start a game in their wake and there would still be enough for the new PCs to do either because the PC's didn't roam very far or else because the PC's did roam widely and so didn't find remotely everything in an area. If you think I'm wrong, start mapping on a 1 or 2 mile to a hex scale and start thinking about how big a square mile really is, and how small a building, a cave or mine entrance could really be.
