How were political borders marked during the Middle Ages?

In some places the borders were very vague zones like a line of hills or mountains or a forest, or a swamp, and in some places they were sharp like rivers and streams, and stone walls between fields.

There are many dykes in Europe besides the Dutch dykes that keep the ocean out. These other dykes usually consist of a deep ditch in front and a high earth rampart behind made with the dirt from the ditch. They were used to mark borders of various kinds in Europe for thousands of years up to the middle ages.

An early medieval Bulgarian khan conquered land from the eastern Roman Empire and marked his new border with the "Great Fence", a long dyke.

The total length of all the dykes in Europe, and the total amount of labor to move that much dirt, is immense. And some of those dykes were made in the middle ages, as I have said.

Another form of border between properties in more or less medieval Europe was hedgerows, which were sort of like modern suburban hedges but more complicated and harder to cross.

In India, the British government built the Inland Customs Line to collect customs fees on merchandise and to prevent smuggling of salt from regions with low salt tax to regions with high salt tax. By the 1870s the line grew to 4,000 kilometers or 2,500 miles long.

In many places the line was fortified with a hedge made of dry dead sticks and thorns that was replaced as fast as possible with a planted hedge of live thorns, "The Great Hedge of India". By 1878 there were 1,109.5 miles of inferior live hedge, dry hedge, and stone wall, and 411.5 miles of perfect live hedge. In 1879 the salt tax was collected at the points of production and the Great Hedge was abandoned.

The abandoned Great Hedge was soon almost forgotten and destroyed by neglect. Roy Moxham, author of The Great Hedge of India (2001) made three trips to India before finally finding a possible remnant of the Great Hedge.

https://en.wikipedia.org/wiki/Inland_Customs_Line1

The historian Procopius mentioned a Frankish embassy to Constantinople and tall tales Anglo-Saxons in the embassy told about Britain. In particular, one story about a wall that ran from north to south across Britain and nothing could live on the west side of it. If a man crossed to the west side he would drop dead. this is commonly believed to be a distorted version of Hadrian's Wall.

But my theory is that it was a barrier separating British territory on the west from Anglo-Saxon territory on the east. Any Anglo-Saxons caught west of the wall without permission would be immediately executed. And perhaps Anglo-Saxon mothers told their children fairy tales about anyone who crossed the barrier instantly dying.

Why haven't archaeologists found remains of this hypothetical death barrier? Probably it connected several different shorter sections into one whole line. Some parts of it would use preexisting dykes, some of which still exist and are known, and other parts might have been wooden palisades. Other sections might have been long hedgerows like the Great Fence of India. Since this barrier line was obsolete before 600 AD, the wooden palisades all were burned as firewood or rotted away in over 1,400 years and the hedgerows would have disappeared like the Great Fence of India disappeared in a tenth of the time.

And it is possible that there might in some places and times have been stones standing along roads marked with the names and/or coats of arms of fiefs and kingdoms at their borders. Possibly there might even have been buildings in some places and times with some sort of border officials.

I would argue that the modern idea of defining a countries as a contiguous territory with well-defined borders, was not dominant during the Middle Ages. Before the modern era, in Europe at least, a monarch's territory was more like a list of places, e.g. I own this county, that city, that village, and so on.

We can corroborate by looking at recent treaties vs historical ones.

Let's look at an example from the Peace of Westphalia (1648), this is even after what scholars considered the Middle ages.

LXXI. First, That the chief Dominion, Right of Sovereignty, and all other Rights upon the Bishopricks of Metz, Toul, and Verdun, and on the Citys of that Name and their Diocesses, particularly on Mayenvick, in the same manner they formerly belong'd to the Emperor, shall for the future appertain to the Crown of France, and shall be irrevocably incorporated therewith for ever, saving the Right of the Metropolitan, which belongs to the Archbishop of Treves.

Note that bishoprics and cities are named but not where the borders are. In fact, the treaty doesn't seem to imagine that there are borders at all. Where are the limits of the "Bishoprick of Metz"? I assume that this is determined by local practices. Other provisions about who owns what are also in this manner.

The Treaty of Tordesillas (1494) did famously define exact borders, but this method of definition were initially only used for territories and colonies outside Europe and not for Europe only. Not to mention the impossibility of marking the borders defined in that treaty.

Compare with the modern day Treaty of Versailles:

The boundaries of Germany will be determined as follows:

1. With Belgium

From the point common to the three frontiers of Belgium, Holland, and Germany and in a southerly direction:

the north-eastern boundary of the former territory of neutral Moresnet then the eastern boundary of the Kreis of Eupen, then the frontier between Belgium and the Kreis of Montjoie, then the northeastern and eastern boundary of the Kreis of Malmedy to its junction with the frontier of Luxemburg.

First of all, the treaty explicitly mentions "boundaries". It still mentions places like the "Kreis of Eupen" and "Kreis of Montjoie", but not in terms of A owns X and B owns Y, but just as reference points to determine exact borders. The borders with Poland (not pasted here, for brevity) are defined in an even more exact and detailed manner.

---

Edit: As promised, here are some scholarly sources that support this view:

For example, Alexander Diener and Joshua Hagen wrote in Borders: A Very Short Introduction (Oxford University Press, 2012)

Although some familiar names, like France and England, could be found on Europe's map at the time, these entities were structured quite differently than their modern successors. Instead of distinct sovereign states, medieval Europe was organized around what became known as the feudal system. [...] Marriages and land transactions between noble families, elaborate inheritance customs, and military conquest further complicated the situation. [...] Given this confused structure, precise territorial borders were not necessarily needed or helpful so long as taxes were collected, services rendered, and oaths fulfilled especially in sparsely populated areas. (p. 38, emphasis mine)

Or Alex Anievas and Kerem Nisancioglu in How the West Came to Rule, (Pluto Press, 2015)

In the Old World, treaties concluding wars typically emphasised nonlinear or noncontiguous territoriality, and the spoils of conquests were divided according to places rather than territories. [...] The first examples of linearly defined claims to political authority can be found in the 1493 Papal Bulls and the 1494 Treaty of Tordesillas between Spain and Portugal. (p.137, emphasis mine)

---

So, my answer to your question is that the concept of "borders" was not very important in Europe during the Middle Ages, so I doubt that there were practices of formally marking borders.