Le mot frontière est un substantif, ici en apposition à vocation qualificative, et il est est naturel de l’accorder avec le nom qui le  précède (ville, poste, place). C’est d’ailleurs ce que reflète l’étude de fréquence. Rien de bien nouveau depuis le Moyen Âge (voir les exemples en fin de réponse).
Cela étant, on trouve quelques mentions où dans cette tournure, souvent perçue comme nom composé avec trait d’union, il reste au singulier. Pour illustration, un article de la Revue savoisienne de 1937 intitulé « Les Bornes-Frontière entre la Savoie et la France ».

Extraits du dictionnaire du moyen français
Place/ville frontiere. « Place fortifiée à proximité du front ou de la limite séparant deux territoires«  : …ledit de Saint Pol alleguoit que (…) d’aulcunes terres, bonnes villes et seigneuries appertenans a sa femme, la contesse de Marle, comme Bourbourg, Dunquerque et Gravelingnes, villes frontieres sur Calais, on luy faisoit difficulté (CHASTELL., Chron. IV, D., c.1461-1472, 80). Et lui pleut [au duc de Bourgogne] (…) le rappeller et le recepvoir en sa bienveullance comme son bon parent et subgect, vaillant et bon chevalier, et de qui bien et grandement se pooit servir (…) car avoit cely de Saint Pol beaucop de belles et bonnes places frontieres entre France et Picardie, et par lesquelles il pooit nuire et aidier grandement a l’un des partis (CHASTELL., Chron. IV, D., c.1461-1472, 212).