The methods of how "medieval lords" kept track of their borders is one that undoubtedly varies greatly depending on the location and time-frame one is talking about.

I can give some insight into how local lords kept track of the borders of their land in pre-conquest England. We have almost a thousand land charters from the various kings of the different Anglo-Saxon people, that is to say the kings of Kent, the South Saxons, the East Saxons, the Northumbrians and Hwicce. These land charters, known to us as the "Anglo Saxon Charters" explicitly state the borders of the demesne of the local lord.

We have hundreds of these land charters, and they are mostly described in a similar fashion. They are often written from the perspective of someone walking around the boundary, and are as such using local landmarks such as combes, valleys and rivers.

The Anglo Saxon Charter concerning Wylye (Grundy number S 469 if you'd like to look it up), for example clearly describes a loop starting at the river Wylye, heading South, West, North then East, ending at the starting point.

Here's the points written out on a table I made.

And here's a visualisation I mocked up overlayed on a topographic map.

If you have any further questions please let me know. All of the Anglo-Saxon Charters are available to search and read online here.