The romanticized image of the lone rider galloping away on a desperate quest isn't wrong, just mostly wrong. A knight left an inn on a different horse than he arrived on, sure...but who ever said he left alone?

Late medieval and early modern travelers who rented horses typically didn't just rent a horse. They also hired the services of a "guide" who would make sure they "didn't get lost" on the way to their next stop. Whether or not the traveler actually needed a guide. Their primary job, as you've probably gathered, was to bring the horse back to their employer.

In a lot of cases, even, the guide wouldn't be on a horse of their own. Several scholars have noted that journey speed was about the same for mounted travelers and travelers on foot. One of the main reasons there is that the enhorsed person was very likely riding next to someone walking.

By the late 1500s in England, at least, it was finally standard for the guide to also be on horseback.Some places, my impression is particularly in Italy, it was more usual to find, by which I mean pay, someone at your destination willing to take ride the horse to its original inn.

As to the prospects of horse theft, especially if the guide is on foot...hiring a horse was NOT. CHEAP. Yes, it would be more, shall we say, financially expedient to steal a horse than to buy one. But in general, you'd have far better and less conspicuous ways of stealing horses than to ride away with one that was pretty well known, especially if you were also somewhat well known. (Of course, lords could also often get away with almost anything they wanted, but that's beyond the scope of the present question.)

You can see, too, how postal systems gradually evolved out of this type of setup. The ruler (or in Europe, the pope was an early adopter) would pay particular inns or stablemasters to always have horses ready for official messengers, who would work out ways to balance horses with the "postmasters" at the next stages. (Probably something similar to the standard practice, although these situations are examples of when mounted travelers can go MUCH faster than people on foot). With frequent enough message traffic, it was cheaper for non-urgent/secret letters to be carried by...well, mail deliverers, who knew the route from their stable to the next stops very, very well.

~~

I’m so sorry, I’d be able to tell you a lot more if it weren’t for apocalypse plague. Late medieval Swiss urban communications is a nonzero chunk of my “books and articles I’ve needed since March” list.

This is a COMPLETELY NORMAL topic to have on your “books I need” list. I don’t know what you’re talking about. Hrmph.

Okay, no, but seriously: there’s this one case where a town wants to execute its former mayor, and three messengers show up as last-minute witnesses who have ridden long and hard and through nights to get there, and—

—No they didn’t. They just jumped in the river and mussled their hair to make themselves look sweaty and exhausted.

I have GOT to know more.