I'd echo Bram and use a grid and actually just for all objects, static and dynamic. You can tune the crap out of it.
As for the grid, it only has to store a 32-bit index in each cell to the grid nodes, like so:
This means you can even store a 100x100 grid (10,000 cells) in just ~40 kilobytes. When elements move from one cell to the next, all you have to do is manipulate some integers to remove the nodes associated (there could be more than one node for a big element) and then insert nodes to the new cells the element belongs.
To avoid resizing the array (vector, i.e.) of nodes (two integers per node) all the time, you can just return them to the free list when they are removed to be reclaimed as needed on subsequent element insertions. That'll make it so you rarely ever have to allocate memory, just manipulate some integers, to move elements from one cell to another.
Here's how you use the nodes as a free list, making their indices double over as a pointer to the next node in a cell or a pointer to the next free node to reclaim.
