If you're world is already build from discrete blocks, then it makes sense to use them as the basis for your navigation.
Pathfinders are easy, fast pathfinders a bit harder. Path following and responding to the changes in the world is the real nastiness.
There are a couple of question which can help you narrow down the potential solution:
- what kind of NPCs you are trying to simulate?
- how long paths are you searching?
- how accurate paths you need?
If you have short paths and you're fine with "better than steering" quality, local grids  are good choice. They are super fast, you can make it work both 2D and 3D. You can get local grid data directly from your volume data, so the nav graph should stay in sync with the dynamic changes easily.
The problem with local grids are that if you have local minima in your world which is larger than your local grid, the agent may get stuck. It is possible to do tricks like add bread crumbs on locations where you detect local minima and try to avoid those locations when searching.
If you need long paths, I suggest some kind of hierarchical scheme. HPA* should give you good ideas how to create sparse nodes in grid a world. Local grids can solve the path finding between the high level nodes. When you make changes to the world, you will need to locally change the coarse nodes too. You can also use the nodes to detect dynamic changes in the game world, and replan the path.
If you have dynamic world, pathfinding becomes statistics. There is no more any guarantees if the agent will find its way. Keeping track of the changes in the world is really hard and replanning when something goes wrong is sluggish.
Eskil rides with this idea in Love MMO, and his path finder is just random sampling with utility function (so is his action selection :)). I would recommend to do that first if it fits your game style.