Best structure for Moving objects?

The ones I have seen used for this are:

Quadtrees
Octrees
Sphere Trees
Hexagon Trees (Not sure if this is the name, but basically using a Hexagon for partitioning, I remember it from an old presentation but I have not seen papers on it)

Avoid structures that are dependent on the spread of objects:
BSPs
Kd-Trees

There are also LABTs (Liquid adaptable binary trees) Yann hinted at them in a post I made (check my profile if you want) involving spatial and temporal cohesion if I remember correctly. They sound perfect for high end games with many dynamic enties

I'm sure if you ask him he'll give a little info. Preferably you would ask him in a public thread so that we all can read it rather than a Private Message.

Another (simpler) alternative is loose octrees, where the octree nodes are loosened so they overlap. I don't have any experiance to share though so I suggest a search around.