Actually, they were used in quite a few games.
Also, voxels are actually a target of the future, not of the past. The problem with implimentation is it requires large amounts of memory (X1xY1xZ1), but overcomming that limitation gives you very realistic objects that can be "opened" and broken apart to reveal the innards.
Pixar's renderman, as well as NewTek Lightwave's rendering engine uses voxels to render smoke, fog, hair, fur, etc. e.g.: http://www.newtek.com/products/lightwave/product/feature_hypervoxels.html
Nvidia has experiemented with rendering voxels in hardware, and there are software packages available to actually use the nvidia GPU to start moving back to voxels.
You can render 100's of bullets in the air with the Havok engine because it interpolates physics objects along a predetermined spline at small intervals with keyframes using bounding boxes for collision detection. The end result is ultra-low CPU usage for objects that are slowly moving and rotating through the air but not hitting anything. It almost costs nothing as far as physics engine (cpu) resources are concerned. Once bullets hit something, it would be one slowly after the other, (not 100's per second), so that also would be a very small to no performance hit.
It sounds like to me, if something hasn't been done before or invented, then you would say its not possible just because it hasn't been done before. Thats the whole foundation of starting and founding your own company. Don't just quit and give up because something is hard, find a better solution and figure out a way to do it.
Something I tell people all the time, "There is always a solution, its only software...".