Minecraft is just one of many games that were directly inspired by the underground hit Infiniminer.
http://en.wikipedia.org/wiki/Comanche_series
Also interesting (historically) is 'Rescue on Fractalus'. Not just for its cheesy name, but also due to its reliance on fractals to draw 3D mountain sceneries:
http://en.wikipedia.org/wiki/Rescue_on_Fractalus!
Edit: videos of both games:
http://www.youtube.com/watch?v=M8opv5u9nf0
First time (as a kid) was shocking...
(To add to the confusion, this particular game, Ace of Spades, actually is voxel-rendered.)
It is however thought that John Carmack's next engine after the Rage engine may include honest-to-goodness voxel rendering: http://en.wikipedia.org/wiki/Id_Tech_6
Historically, Carmack has had quite a lot of influence on both the hardware and API vendors, so it will be interesting to see if he can spearhead more mainstream movement towards sparse voxel octree rendering: http://youtu.be/THaam5mwIR8
The iPhone wasn't the first smart-phone, it wasn't even the first touch-screen smart phone, but most people (correctly) give it credit for popularizing the style, and creating a new "genre" for smartphones.
Edit: Well, ok, I don't want to put it in such absolute terms. But I do think that Minecraft deserves quite a large chunk of attribution for the genre.
Minecraft is also not a voxel renderer. Voxel renderers typically work by casting rays against the grid. Minecraft draws the blocks with rasterized triangles, using a hardware-accelerated 3D API (LWJGL), just like almost every other 3D game.
In other words, there is practically no interesting overlap between what NovaLogic was doing, and what Minecraft does.
I remember this epic duel I played vs 2 other guys (yes my teammate quit) in a castle type map. Since I turtled too heavily for them to break through, eventually they just drowned me by blasting me with arty long enough for map's floor to erode beyond water level.