What does "constantly moving" mean?
For example, if these points represent particles moving with a constant velocity and only affected by hard-sphere collision with other particles and with the wall, then it's possible to compute the time to intersection of each particle with the bounding box, and the compute the time for next collision. The time for next intersection can be kept in a priority queue, and when an intersection or collision occurs, you need only compute, in O(n) time, the next intersection of that particle/those particles with every other particle.
The mechanics of this are outlined in http://introcs.cs.princeton.edu/java/assignments/collisions.html , and summarized by Karl Bielefeldt earlier.
If the movement is random, but the changes are small and bounded then there's an upper limit on how far things can move. Use that as a bound. For example, if the max speed is 0.1 units per evaluation and your bounding box is the cell (10,10)-(11,11) then you can easily determine the particles within, say, 10 units of that cell, and know that there's no way any other particle can reach that cell for 100 evaluations.
If the coordinates change drastically each and every time, then the O(n) linear search is the best solution because any data structure (quadtree, hash grid, etc) takes at least O(n) time to set up, if only because it needs to visit each point.