On is used if something straddles the border. Like a house (such a thing does exist) or a town. If one part of the entity is in one country, and the other part of the entity is in another country, then it's on the border.
Niagara Falls is an example of a city that has part of it in one country (the US) and the other part in another country (Canada). Niagara Falls is on the border.
I believe there are actual places where there is a visible line that demarks the two sides. In such locations, if a person were to have one leg one side of the line, and their other leg on the other side, then the person would be considered to be on the border.
In most places, however, no such physical border line exists. So, for most people in most places, the entirety of a person is either in one country or the other. As such they are at the border. This is the used in the same way as when you say that somebody is at the door, or at the gate. That person is standing somewhere with something visibly in front of them.
Alternative prepositions to at are near, nearby, next to, and close to, all of which are actually more appropriate if two things are some distance away from each other.
I have no idea where South Ossetia is, but it sounds to me from the description that it's located entirely within a single country. As such, it should not technically be on the border, but at the border—or, depending on how far away it actually is, one of the alternative prepositions could be more appropriate.
But while that's a literal interpretation of the prepositions, people do still say that a place is on the border, even though that's not literally the case. Figuratively speaking, it's "close enough." So, you wouldn't be faulted for using either on or at—even if South Ossetia belongs entirely to a single country.