Re: raytracing stars, the obvious answer is to use a lower detail representation when the stars are far away. In this case all the photons from the faraway galaxy will be arriving from almost exactly the same direction, so there won't be any noticeable loss of accuracy. This fits in pretty naturally with the hierarchical data structure you'll already be using (in practice) to hold the scene.

Regarding the data structure: the types of hierarchical structure commonly used to hold scene data for ray tracing actually lend themselves pretty well to level-of-detail, caching and streaming from disk; so it can be a help rather than a hindrance for managing memory. There's been some really promising work in the last few years on Sparse Voxel Octrees, for example.