Well, all games have a story, except maybe super abstract stuff like Tetris. Doesn't mean it's elaborate
There are plenty, thousands of video games with no story at all. Vast majority of games of any genre in the first years and since then most strategy games, sport, simulators, "social", etc.
In regard crpgs, Darklands, Mount & Blade, Kenshi, Neo-Scavenger or most rogue-likes have no fixed narrative at all. Additionally there are some games with some sort of fixed story, but the limited sense of urgency -even Fallout time limit is not enough-, the amount and quality of non story-based content and the open exploration stimulate players to enjoy that secondary content as equal or more relevant for their experience than story.
Ahh to have a good exploration you need a good story/mystery to solve. You don't just explore to find a bunch of mushrooms or some ammo. The game have really good setting that evokes the player's inner curiosity.
Exploration don't depends on story at all. In most cases good exploration is achieved besides or despite that story. In the few cases in which good exploration is linked with some narrative, is not the story itself what makes exploration good. There are even some examples of good exploration in games with no story, as the aforementioned case fo Kenshi. Also "setting" and "mistery" are not the same as story -again with Kenshi example, very good setting and many misteries with no story-.
What makes a good exploration? Mostly three perspectives, in order of relevance:
1. Good exploration specific mechanics: movement, locations search, survival and travel options.
2. Good level/world design: rewarding loot, secrets, hidden rooms, traps, content only reachable with some specific tool or mechanic, etc-.
3. Good worldbuilding: detailed, unique, diverse or intriguing locations/enemies/objects.
Only first two points guarantee a good exploration. Games with poor worldbuilding but great level design and mechanics -many blobbers and other dungeon crawlers- can have a great exploration, while games with good worldbuilding but shitty mechanics and "level" design -The Witcher 3 or Skyrim- kill exploration with quest markers, witcher senses, world leveling or enemy-loot placing and reusing.