Hmm, have you listed the collision geoms to see how they are indexed. Depending on the types of space used, they may already be indexed in a certain order. I'm sure they're indexed based on their size in hash spaces.
You can also try using dSpaceCollide2(geom1,geom2,world,group) to check collisions between two specific geoms (or spaces).
You can also try using dSpaceCollide2(geom1,geom2,world,group) to check collisions between two specific geoms (or spaces).