Thanks for your comments.
I will try to implement the method Riven suggested.
Recently I thought about another tree to implement a scenegraph:
R Tree The wiki entry is not so good, so if you want to know more read this
paper.
This tree is made to handle spatial data in multiple dimensions.. in this case it's only 2 dimensional and would hold rectangles. The nodes itself can overlap and their boundaries can grow, if you add new items to a node. The tree supports searching in areas for example questions like: which nodes are inside this arbitrary rectangle. If a nodes covered area gets to big, it's splitted up in smaller nodes similiar to quadtrees.
Advantages: moving objects just cause a node to grow, the don't leave the node -> this means you have to check the size from time to time, if it's to big -> split nodes
Disadvantages: I guess collision detection doesn't work so well, or is harder to implement
I didn't test this kind of tree yet, I just had spend a couple of moments to think about it.. what do you guys think?