I would add this as a comment in response to @Nathan Reed's answer, except it's too big to be a comment, and is perhaps in any case worthy of being a separate answer.
We were doing precisely what was proposed in his answer, and in fact have comment in the source linking to this page. For the most part, it has worked extremely well, except that once every two or three months, we've been losing a server at random that has gone non-responsive due to massive duration of search queries.
The root cause of the problem came to my attention while doing a performance check to try and figure what was causing this. It's likely only a concern if you permit overlapping objects. In our game we do, and in a worst case scenario it occasionally lead to a performance killing depth spike.
We had one edge case where about 100 objects, all with with bounding disks, were clustered in very close proximity. That lead to the problem of a very deep spike in the tree, because we got to the point where objects were larger than the area covered by the quadtree nodes, so each new object was showing up in multiple nodes, leading to massive subdivision of the tree, thus snowballing the problem out of control.
The takeaway from this is that if you allow object regions to overlap, keep a close eye on things if you get tight clusters of objects, to ensure your tree doesn't get too deep.
The solution I'm currently investigating is to store objects as points, and then when doing a search, increase the bounds of the search rectangle by the maximum radius stored in the tree. That should work for us, because the tree is a first pass search, we then do a true circle based range check, along with a few other criteria checks, so the extra false alerts will get filtered out.
Your actual mileage may vary.