The technology wasn't ready.
Minecraft was groundbreaking in optimizing the handling of destructible maps. This was during a time where every other game were trying to do realistic graphics. Using blocks or voxels was considered silly because it couldn't ever look realistic. The game Delta Force used voxels for the landscape and even if it looked nice for that, it also showed that the use of voxels was not ideal for detailed realistic graphics.
Destructible landscape was used in 2d games like Worms, but that was basically just a bitmap image, so it didn't require much memory to keep track of the limited map size. Minecrafts map is theoretically infinite, and while some other games also had chunk loading, it was new that the game was able to save the precise state of all the unloaded chunks. The magic is that the game only saves changes that are made. The rest of the map is procedurally generated, so it doesn't have to save everything. It can just recalculate the map and apply the changes. No other game did this.
Gameplay wise, the survival game Stranded was close but it was limited by using ordinary polygon graphics, so while it had crafting and some mining (gathering materials), the map itself was not destructible. It also had a storyline so it wasn't as much of a sandbox game.
So basically, Minecraft combined a lot of different technologies to make it possible and it was only possible because the graphics were grossly simplified. It started as a hobby project and I doubt that any AAA publisher would have funded it at the time, because the idea of block voxels was so far out.
I remember waiting and waiting for an MMO named Atriarch that never came out - it seemed impossible, player created structures in 3D? Years later I remembered Atriarch and realized it's dreams had kind of been achieved by Minecraft.
Infiniminer came before Minecraft and was what directly inspired Minecraft. Off the top of my head UnReal world comes to mind as a survival and sandbox game in that vein and it came out in the 90s. It wasn't a super popular genre at the time.
I'm still playing URW. Game is sick! Tough as nails....until you figure out how to cheese it.
There was Wurm online which was a complicated messy sandbox MMO. I also remember plenty of physics and combat sandboxes in the Flash space. Sim City was a city builder sandbox. As for block building sandboxes there was Infiniminer.
As for survival, many games have had survival elements. A core mechanic of roguelikes is something called a hunger clock. It doesn't necessarily have to be food based but the idea is a game that is about exploration and conquest having a mechanic that limits exploration creating tension where you have to explore with purpose instead of meandering. Some MUDs might be able to be seen as precursors to massively multiplayer survival games like Rust.
Survival games existed before Minecraft but in a very different form.
Survival Kids is a konami series of games that started on the GBC and went on to have 3 more episodes on the DS, where the premise is always "you're stranded on an island and must find a way to be rescued", but unlike modern survival games, the world is custom built and the evolution of the plot is usually pre-determined, with maybe some branching but nothing extremely dynamic. You also couldn't alter the game world in any significant way beyond what was already expected, such as building bridges in predetermined spaces and so on.
It has some hallmarks of the later versions of the genre, like an emphasis on crafting and needs management such as hunger and thirst, so the connection is definitely there.
Terraria, though similar release date? Highly recommend the don't starve series a few years later. It's quite different as far as game play though.
Hunter was an early sandbox game on the Amiga and was quite good back in the day. Mercenary series too. Daggerfall was/is a huge sandbox rpg. Minecraft was the first to capture the lego style creativity though. Dwarf fortress is probably the closest to Minecraft.
Minecraft kind of started it. Maybe Roguelikes such as Nethack? They certainly had the survival elements, although were much more brutal. That's as close as I've ever seen that could be comparable to Minecraft or survival sandbox games prior to Minecraft itself. It feels like if it did exist, it would be known by a Euro gamer; all the crazy cool complex games from really early days of gaming I have found were made in and popular in Europe, but didn't see much action here in the states.
The closest games that come to my mind are Schiffbruch and Stranded.
