I've been working on a physics engine for XDX (I know, it's excessive, but I want to learn how to make *every* component of a game). Spatial partitioning has been getting me down - in particular, octrees are painful because of all the edge cases that have to be considered - especially when one cannot restrict the system to a given space...because I'd rather my games be able to handle "infinite" space.
Last week, I found the answer to all of my problems: spatial hashing. It's a really beautiful scheme, and since it uses a uniform grid for the partitioning, it's particularly simple to implement. However, the fact that grid cells are hashed to buckets means that the flexibility is unrivaled: not only can one specify the size of a grid cell, but one can also specify how many buckets will be used to attach to grid cells. The system easily handles infinite space (since the hashing function works for any x,y,z triple).
I'm pretty excited about the implementation of this collision detection system, and I can't wait to see what kind of results I get! Physics-enabled space games may not be so far off for XDX!