Anything that is either hierarchical and/or sparse should help you out here.
There's a lot of empty space, so not having to use storage to represent empty space is a must. A typical hierarchical approach would be something like an Oct tree which recursively subdivides space into 8 smaller cubes, and you can store objects in the smallest cube that they can completely occupy.
An octree is also pretty good for you being able to query it for a list of all objects in a view frustum which will let you get a list of only the objects that are within your viewing angle and aren't too distant. A sparse solution could be something like a sparse grid where you can ask for information about any x,y,z location, but you only have to store information for cells that aren't empty space.
Other common hierarchical approaches used include bsp trees (they split space into 2 half spaces recursively) as well as k-d trees which do similar.
I personally think an octree could be a good start for you, making sure to subdivide only as deeply as needed so you don't waste memory on empty space. also, you might end up wanting a different solution for your static objects versus your dynamic objects.
Some solutions (like bsp) can be very efficient, but take a long time to construct so aren't usually a good choice for moving / changing objects.
Hope that helps, let me know if you have any questions about the details!
infinite universe
could be similar to tracking relationships between two points on some Mandelbrot curve after zooming to different levels. At some level, you can lose precision and be unable to distinguish them or even locate them again. \$\endgroup\$