Actually, that's the important point. The rules don't actually say what "starlight" or "bright moonlight" is.
So, if on a particular cloudy night, it's bright enough for a human to have 5' shadowy sight, that means a human is blind beyong 5' (where there's total darkness). For the record, that's really, really dark.
A much more reasonable assumption is that, on a relatively clear, full-moon night, everything has shadowy illumination. That means everyone has line-of-sight to the horizon, but everything has concealment. Creatures with low-light vision, however, treat it as full daylight.
From here, you work backwards. More clouds or a less-full moon brings the edge of LOS back to 1/2 way to the horizon, meaning low-light vision creatures still operate normally.
You should be careful with how far you bring the horizon in, however, because it can lead to pretty ridiculous results, as the 5' shadowy discussion above demonstrates.