(disclaimer - I'm not an expert) They're probably using some kind of sparse octree for looking up points. That means they split the space with planes into areas with high concentration of points and empty ones (then split the full ones more). These kind of structures are not easily update-able as far as I know - or if you update them in trivial way (move the boundary), they could lose the fast lookup properties. It's a bit like with global illumination - you have to precalculate a lot of values to render the scene in a reasonable time later on.

It would be interesting to see if anyone can create a hybrid of point-cloud scene + polygon animation... should be enough for most shooters. (Outcast apparently had something like that, but that was pre-"nice graphics")