A few years ago I read a paper on this topic about the messengers in the county of Artois in the early 14-th century(so a call for full text if someone knows it - Small, Carola M. "Messengers in the County of Artois, 1295-1329." Canadian Journal of History 25.2 (1990): 163-176.) . While a bit late for your question, it might be relevant.

So, on to the relevant bits - different powers organised their messaging differently. On one hand you have organized mounted envoys, that were employed by the English and the French crowns in The XIVth century. On the other, horses are expensive and require infrastructure to use efficiently as messengers. On a bad road a horse would not be much faster than a pedestrian, and even when running, horses can get tired pretty fast (not to mention injured), so you would need to get a fresh mount. And horses need feeding and watering too.

For most purposes, and even urgent messages a pedestrian was more suitable, and seems to have been the preferred method for many nobles and the common folk. These would rarely be dedicated professionals like your modern mailman. They would instead be someone either recruited for a particular job (like a trusted person that you can send to the lord next village), or a person who happens to go a certain way. Depending on circumstances such people might not even be paid but do the job pro bono or in exchange for services.