Collision detection in FSO was never that bad.
We perform quite a few first-pass optimizations in order to cut down the number of collisions we evaluate (like, for example, primary weapon shots will never collide. Or things like a weapon moving away from another object. Stuff like that.), and once we get into actually having to evaluate collisions against another object, we go through a BSP tree to quickly evaluate them (this is the reason why the pof format is as omgwtfhuge as it is, BSP trees are efficient to evaluate but not efficient to store).
Basically, our collision detection is usually much better than O(n log n). The issue with large models such as the ones under discussion is that evaluating the BSP tree takes ages, and once we go into it, it is almost guaranteed that we'll be going through it all the way.
That's how collision meshes work: By not evaluating collisions against the main mesh, everything speeds up by a lot.