This is the kind of problem that CUDA would be great for. Should be very amenable to parallelisation.
I don't understand how the voxel objects can collide internally? Does that mean they're not static? I'm imagining a kind of Lego construct. Or is it that the various objects are created from static voxel objects that are hinged together at various joints?
Maybe you could use an existing physics engine to create a bunch of bounding boxes around your voxels. At the simplest level, you could just create a 3D grid pattern around each one. Then when the boxes from different objects collide, do an n³ collision check at the voxel level, where n is hopefully small.
I tried to draw something in Paint but it didn't look like anything