I think probably you could do something with quadtrees, for if some circles don't cover all the grid cells at first:
you could keep making the grid smaller until either they do:
or else you find a point in a not-necessarily covered square that actually does have some acceptable space.
And I think you can probably speed up the point sampling by doing it more locally, treating the arrivals process as a 3d poisson process in spacetime, and taking longer, skinnier, more timey-wimey bits
that nonetheless have the same volume, and taking a geometric distribution to determine how many arrivals are in that chunk, and the uniform distribution over where they are in the chunk.