Later, I did a quick test (1 hour of coding) to apply the same idea in the GPU (pixel shaders 3.0). A simple voxel was setup with a few primitives (at 128^3 resolution again), and a brute force raymarching algorithm applied again. Result, 60 fps at 640x480 with no interpolation at all. The image below shows the result of the test. The volume contains only one single blue sphere, but cause I set the wraping mode to "repeat" (GL_REPEAT), then the volume gets virtually infinite, and that's why you see several copies of the scene.
An obvius improvement is to store the distance to the closest point per voxel, instead of just the inside/outside information. But that's more related to the "rendering with distance fields" technique.