Do we have evidence of any states or smaller societies building border walls or establishing checkpoints? Were armies ever permanently stationed around clearly-delineated territorial borders?
You might be interested in here specifically /u/Tiako's question about pre-Columbian frontiers.
/u/Mictlantecuhtli answer:
Depending on the people being studied, frontiers can be seen. The most evident frontiers I know of within Mesoamerica is the boundary between the Mexica (aka Aztecs) and Purepecha (aka Tarascans). Both groups had battles over a number of years, but when it became evident that neither could conquer the other at the present time they began to build a series of fortresses and defensive locals to defend their territory. Caught between them were other ethnic groups like the Otomi who often acted as traders between the different groups as evident in the Purepecha having Pachuca obsidian from Central Mexico.
Less clearly are the borders between Maya city-states in the Classic Period. Defense was not a very important issue until the Late Classic when we begin to see settlements and cities abandoned. Some of these places had walls constructed around the elite center like at Aguateca. Defensive walls became a more prominent in the Postclassic such as at the site of Mayapan which is entirely encircled by a wall.
Within my own area in West Mexico frontiers are a little iffy. There does not seem to be hardline boundaries between other groups like Teotihuacan. Rather we see artifacts and architectural styles within a limited range. Shaft tomb figures and guachimontones are not found in Veracruz, for example.
and /u/snickeringshadow answer
I also figured I should expand on the boundary question by talking about the most well-defined frontier in Mesoamerica: the Aztec/Tarascan border.
During the reign of the Tarascan emperor Tzitzispandaquare, the Tarascans invaded the Toluca Valley, which at the time was subject to the Aztecs. The Aztecs responded by retaking the Toluca valley and followed it up with a full-scale invasion of the Tarascan empire. They sent an army of about 30,000 across the border and made it about halfway to the capital before the Tarascans ambushed them with a much larger force and completely annihilated the Aztec army.
Following this, Tzitzispandaquare implemented a new frontier strategy to prevent the Aztecs from ever launching an invasion on that scale again. The first part of this strategy involved the construction of a series of fortifications along key mountain passes along the border. Each border fort was within communication range of other forts, to allow for coordination of defense between them. Shirley Gorenstein actually argues that the forts communicated with each other through the use of signal fires, although this isn't proven.
The second part of the strategy involved garrisoning the forts with refugees from the Aztec side of the border. The Aztecs implemented a strategy of collective punishment against those communities which sided with the Tarascans during the conquest. The classic example of this is the town/city of Oztoman, where the Aztecs either killed or exiled the bulk of the population and replaced them with ethnic Mexica from Tenochtitlan. As a result of these policies, large numbers of refugees fled Aztec occupation for the Tarascan side of the border. Tzitzispandaquare apparently struck a deal with these refugees to give them land along the border with the understanding that they would garrison the forts.
The result was a network of fortifications along the Tarascans' eastern border that had permanent garrisons. These forts were supported by watchtowers and an expansive spy network that notified them long before any potential invader reached the border. If an invading army arrived, the forts would notify the capital and the capital would send reinforcements before the fort fell.
This is one of the only (if not the only) examples of a "hard border" in Mesoamerica. Even individual people were not allowed to cross it without prior authorization from the Tarascan capital. Embassies from Tenochtitlan had to present themselves at a border fort and wait for clearance from the capital before crossing.