Pathfinding & Navigation in 3-dimensional space (proced. generated)

What would be a good way to realize pathfinding for AI enemies in a minecraft-like environment that
a) is fully three-dimensional, with rooms above rooms and son on,
b) will change every now and then when blocks get deleted or added by explosions etc.

So far, I only have experience with grid graphs and I think they’re not a good solution. Would Nav mehses somehow work, or are there evern other methods? What about flying enemies? - this topic may be useful

Pathfinding in a voxel environment is actually really nice on the programming side because the whole world is already sorted on a grid. So you don’t need a grid graph or anything. All you have to do now is to use a pathfinding algorithm like tha a* (A-star) algorithm to generate your path. You might want to check out my voxel engine on the unity assetstore. It already comes with a pathfinding system: Unity Asset Store - The Best Assets for Game Making