Technically you could still have a randomized non-voxel terrain.
I've programmed a fairly basic game in unity that randomly generated large maps with randomized 1 story buildings \ layouts. Been a few years, from what I remember the navmesh was pre-baked into each "block", but the blocks were on a 2d plane with varying elevation. There wasn't any "blocks" above or below, so it saved a ton of calculations on generation. It was fast enough that I could randomly generate while the player was running.
Mind you I never got any textures in and AI pathing was fairly basic, but it worked pretty well considering I was a novice and only spent about a month on it.
Either way though, like you say this game would certainly a lot more generic without randomgen. I could care less about mining, but the randomized maps are the main draw of the game for me and my group. Nav got boring after a couple of hours, so I don't see even having 4 or 5 times the size of the map being enough to hold my interest.