You are right: to find a location from a star image you need a true horizon, but unless UAV is pulling some Gs even a basic accelerometer would give you the horizon, accuracy of that estimation will limit the accuracy of your location.
Regarding satellites: so "starting with the slowest moving" requires a series of images, doesn't it? Then how do you know "your approximate location"? From stars? In theory I understand what you say but practically it would be much more complicated and the obtained accuracy would not be better than with the stars, since in either case you also need a horizon to know your location.
No you just "start looking" on a single image.
Know your approximate location: by dead reckoning. You will need coordinate fixes once every few minutes anyway and you know your direction precisely enough from the same stars, error only comes from wind direction not being precisely known. So we are speaking of correcting for at most tens of kilometers of error. 10km at a typical distance of 1000km to a low orbit sat is <1 degree and only about 10 arcmin to a typical medium earth orbit satellite.
Astrometry allows for locating objects down to about 0.2 pixel reliably and to 0.1 pixels in optimal conditions, so a typical wide-angle camera that might have about 40 arcsecond pixels will easily give 8 arcsecond precision, for a satellite 4000km away (about 2000km orbit at 30 degrees elevation), that's 170 meters of location error, which is more than good enough for navigation (final targeting is done by optical pattern recognition on the ground anyway).
>since in either case you also need a horizon to know your location.
No you don't. Benefit of using satellites is that the source of coordinate data is the parallax of satellites vs stars. It works without having a vertical/horizon.
Simply put, we calculate that in a predicted location the satellite will be at a certain pixel distance from a few of the closest stars on the photo. And it will be a few pixels off that predicted point. Distance and direction of that error allows for calculation of discrepancy of predicted vs real location (and repeating this process on several satellites visible on same photo, allows to decrease the error by removing outliers - which might be noise/space rays on images or errors in star catalogs or orbital elements data, or satellites changing their orbits - and averaging the results).