My biggest problem with this explanation is that even if the star-filled universe were infinite that doesn't necessarily mean there would be a star at every point you look at in the sky.

Depending on the density of the stars in space, it's quite probable that as you zoom in farther and farther you see more and more distant stars, you also see space between those stars. It becomes a limit problem where the 'star density' of the sky (vectors from your viewpoint which will eventually hit a star) gets closer and closer to a specific percentage the further you extend your sphere of view (or magnification level) but will never exceed it, and won't ever go to 1.