DMGregory's point about voxelization's simplicity seems about right.
Another reason though, is performance. With these navmesh algorithims, you need a way to reduce the complexity of a scene.
Voxelization is a way of reducing the complexity of high poly meshes. Additionally it has the same effect as spatial partitioning whereby the number of potential neighbors of any feature (triangle/voxel) is reduced to a small, finite amount. You can imagine, depending on the mesh, that a long triangle could require intersection checks with a large portion of the scene, while that will never be the case with a voxel.
If you're interested in different approaches then Recast, here's a video by Casey Muratori in which he explains the (real-time) walking system he developed for the Witness. From what I remember, instead of voxels, he uses sort of poles to quantize the world (thereby simplifying it)