Spatial Structure for moving objects

You didn't say the size of the maps so a uniform grid is a good solution for smaller maps. Moving objects and bullets like in an FPS can use grid transversal for ray casting or moving lines. (look into 3DDDA). Also insertion and removal is usually very quick for tons of moving objects. Also it can hold static objects so you only need one system.

(if size is an issue and you are good with theory, a nested grid unlike an octree will allow for easy grid transversal, but it's harder to code)

Try any of the following:

- Loose Octrees
- Uniform grids (if you do it smartly you can have O(1) lookup for broad phase collision detection), look at the book Real-Time collision detection
- Fixed size quadtrees
- Sphere trees
- Plain old manual section partition (Divide your level on sections manually placed, and traverse the sections one by one at runtime)

Adaptive methods are not a good choice for dynamic object space partitioning, kd-trees are probably not a good bet either, they are really not better than fixed size octrees for this type of problem, they would be good for static geometry though

I'd suggest looking at a proximity map (hierarchial grid that is offset at each level to prevent the "plane of death" scenario where an object bubbles to the root of the structure when it crossed a plane common to multiple levels). I think it was presented at GDC 2005 by one of the guys at Ready at Dawn (ex Blizzard I believe). It is exremely fast for both query and updating.