So basically, how would the medieval lords communicate with each other? Would they just send some men in horses and hope the message got sent? And in times of war, when the danger was bigger?
Yes, you would send a messenger or messengers with a letter. Both were important.
The physical letter, whatever its actual contents, served as the sender's presence-by-proxy. In an difficult but crucial article, Brigitte Bedos-Rezak established that it was the lord or king's seal on the letter, in particular, that functioned as the remote lord. It's not a sign of the sender's approval of the contents, or (just) a means to make sure the letter wasn't tampered with; it meant the sender wanted to be understood as physically there.
The messenger was equally important, because letters themselves couldn't be trusted not to fall into the wrong hands before or--especially--after delivery. So generally the messenger would have the rest of the message to convey in person. (Presumably they were very good at making things up under torture if necessary?) We know this because some letters actually direct their recipient to question the messenger in a specific manner!
Although, one interesting thing about the letter-as-presence is, sometimes the actual contents of the letter/message didn't mean much. It was much more about keeping up the relationship: the letter would be meant and perceived as basically a personal visit without the expense and inconvenience of travel or hosting a guest.
Of course not all letters reached their recipients. This is perhaps a more extreme case, but Spain and Ethiopia spent the 15th century trying to arrange a marriage alliance via letter-messenger. Unfortunately, most of the surviving letters say, "We never heard back from our last one," and traces of the messenger that we can track might disappear, as in one case somewhere in the Black Sea region.
The earliest organized mail delivery system isn't set up until the Holy Roman Empire under Maximilian I, and even then and when it is revived by Charles V, it was mainly for the benefit of particular meetings of the Reichstag and the need of princes to attend (in person or via representative) while governing at home or at war against the robber barons in their principalities.
Were carrier pigeons used?
Reading Clavell's Shogun at the moment, this portrays regular use of carrier pigeons (and indeed hawks to intercept them).