As apatriarca said, two spheres may collide even if their orbits don't intersect (and in reality orbits in 3d, which are just lines, will rarely intersect, unless you impose restriction of being on the same plane).
But you can do a sort of hybrid approach with the region idea you mentioned originally. There's two ways I can think of, off the top of my head, depending on how much data overhead you can afford.
One is to separate your space into an imaginary rectangular grid, where each cell is size NxNxN. Then, at startup, traverse the orbit of each sphere using equations for an ellipse, my suggestions is using parametric form). Each little jump you make along the ellipse (make sure jumps are of size N/2 at maximum), record which cell your ellipse passes through. Then, account for the radius of the sphere travelling along the ellipse, and record the other cells which your sphere will fall into, if it were at that position on its elliptical orbit.
This way, for each cell, you'll have a list of spheres that can possibly pass through that rectangular cell, and you only have to check for collision with those, making sure you don't repeat collision checks (so if you're on sphere A, and just checked if it collides with sphere B in that cell, don't bother checking if sphere B collides with sphere A). The problem with this is that it requires a lot of overhead, especially if you make your grid too small. And if you make your grid too large, you'll start having to go through a lot more checks - so there's a sweet spot depending on your setup.
Note: I just realized that the next method assumes all your ellipses have one common (or very nearly so) orbiting point, like planets around the sun, which may not be what you meant
Alternatively, instead of making a rectangular grid, make spherical shells, of certain thickness (again, varied depending on your setup, and again having a sweet spot of being neither too thick, nor too thin). You can easily calculate the perihelion and aphelion of each elliptical orbit (and add/subtract the sphere's radius) so you will know which of these spherical shells your sphere can pass through. Then when performing collision for a sphere check which other spheres pass through the same spherical shell in which your sphere currently is.
The upside is that you'll need a lot less data storage here, than in the cubical grid method. The downside, as I mentioned in the note, is that this will really only work well when all your elliptical orbits have a common, or nearly common, orbiting point.
