I'll throw in another vote for a loose quadtree. The 'loose' variants work nicely when many objects are moving by allowing a little more leeway before you need to shuffle; but ultimately if it moves far enough a shuffle will occur.

When you write that you are looking for "better ideas" than the quadtree, you're going to need to be a little more specific about what makes a quadtree not work for you. Having a lot of moving objects is going to be a concern for all systems. It doesn't matter what structure you are using if you must restructure a million-entry tree every update, that is a lot of work no matter what you choose. There are many variants of the common data structures that trade off issues like random access vs pointer chains, exchanging data size for lookup speed, reducing the volume of data that changes during movement by adding a layer of indirection, and many more. If we knew more we could probably help figure out some of the tradeoffs you might benefit from.

In other words, so that we can help you better, what SPECIFIC properties are you concerned about, and what SPECIFIC properties of your data make you think it is a problem?

Frob: I completely understand your concern. I'll defer an answer until I've tested it in practice.

I just like to plan in advance before I start writing code to minimize wasted work, this thread is a symptom of that.