Since the word heretic or heresy actually means to choose, why did St. Mark call the Latins of his day heretics?
Here are a few notes I started a while ago on LXX, Rabbinical, NT and early patristic usage; even here we see a departure from the sense of "choice," which was according to Kittel already just an occasional usage as early as the LXX (Kittel, ed., TDNT I, p.182). These should also be compared to medieval developments -perhaps more if time permits- but early developments and their historical contexts are already both interesting and instructive.
The LXX most often uses αἵρεσις to render מִין/min (cf. kind/species, as in "after their kind" in Genesis). Philo and Josephus use αἵρεσις without negative connotations. In Philo it is used of a Greek philosophical school and the "august philosophical society of the Therapeutics" (ibid, 181); Josephus uses it of all religious schools, trends, and parties within Judaism (e.g. Essenes, Sadducees, Pharisees etc.) and Greek philosophical schools. In the first and second centuries AD Rabbinic Judaism began to restrict usage of מִין: "when certain minim [plural of מִין] separated themselves from the orthodox Rabbinic tradition it came to be used only of trends within Judaism opposed by the Rabbis and therefore sensu malo
. The term thus stigmatized certain groups as heretical. This sense is found in Rabinnic writings belonging to the end of the first and the early part of the second century" (Kittel, ed., TDNT I, p.182).
A qualified/limited negative Jewish appraisal of Christianity as an objectionable heresy is evident as early as Saul (later the apostle St. Paul) in the book of Acts, the stoning of St. Stephen, stonings/beatings of St. Paul etc. the seeds of which we can see growing as early as Saul before his conversion to become the apostle Paul, the execution of Stephen, stonings and beatings of St. Paul etc.), however at the same time Jewish Christianity continued to operate to a significant degree within the context of second Temple Judaism in Jerusalem even after the stoning of St. James in the late sixties and to a lesser degree even after the destruction of the Jerusalem Temple by Titus in 70 AD when millions of Jews were also massacred by the Romans.
Especially important, perhaps as early as AD 90, or as late as the early 100s, is the addition to the Eighteen Benedictions (standard prayers read aloud in synagogue services) read aloud in synagogue services to facilitate exclusion of Christian participation in synagogue worship: "For the apostates let there be no hope, and may the arrogant kingdom be uprooted speedily in our days, and may the Nazarenes and the heretics (Heb. minim) perish as in a moment and be blotted out of the book of life, and not be inscribed with the righteous. Blessed art thou, O Lord, who humblest the arrogant" (12th Benediction or Birkat Ha Minim; this 12th Benediction is preserved in multiple versions).
What is usually thought of by historians as the final breach between Christianity and Judaism, and between Jewish Christians and their fellow Jews arrived a little later though, in AD 135 after the Nazarenes had refused to take part in the Bar-kokhba uprising on grounds that it was impossible for them to recognize his messianic claims (there could for them be no other Messiah than Jesus).
It is during the same period we see a gradual change in Christian terminology. However "the development of the Christian concept is not wholly analogous to that of the Rabbinic מִין, as though in the process of the separation of non-orthodox groups, the heterodox parties came to be designated heresy... The usage in Acs corresponds exactly to that of Josephus and the earlier Rabbis... (TDNT I, 182, e.g. Acts 5:17 αἵρεσις τῶν Σαδδουκαίων/sect of the Sadducees; cf. developing negative usage e.g. in 1 Cor 11:19 αἱρέσεις ἐν ὑμῖν/factions among you; Gal 5:20 ἐριθείαι διχοστασίαι αἱρέσεις/disputes, dissensions, factions/heresies; 2 Pet 2:1 αἱρέσεις ἀπωλείας/destructive heresies, brought by ψευδοδιδάσκαλοι/false teachers ἐν ὑμῖν/among you, etc.). There is a theological reason for this development (or, if you will, unfolding)...
A very "Orthodox" observation (I think) by TDNT is that the "basis of the Christian concept of αἵρεσις is to be found in the new situation created by the introduction of the Christian ἐκκλησίᾳ [church]. ἐκκλησίᾳ and αἵρεσις are material opposites..." In contract to another NT word σχίσμα/schisma, i.e. schism (often translated "division") heresy "obviously indicates something more serious. The greater seriousness consists in the fact that αἱρέσεις affect the foundation of the Church in doctrine (2 Pt 2:1), and in that they do in such a fundamental way as to give rise to a new society alongside the ἐκκλησίᾳ. This, the Church cannot accept, since as the lawful public assembly of the whole people of God the Church embraces this people exclusively and comprehensively. By its very nature, however, αἱρέσις is a private magnitude with a limited validity" (ibid, p. 183). In the early fathers, e.g. Sts. Ignatius and Justin, αἱρέσεις are "opposed to the ἐκκλησίᾳ... what the Church usually has in view is Gnosticism. As seen by the Church, the Gnostics form schools" (ibid, p. 183; cf. also in this regard the pluralization, fragmentation, and the crisis of legitimization in Western Protestantism since the Reformation).
In this connection we are already reminded of the Nicene Creed's emphasis that the Church is one (a notion already, of course, having firm roots in the NT), as also reflected in St. Vincent of Lerins' concern thatt “all possible care must be taken, that we hold that faith which has been believed everywhere, always, and by all… This rule we shall observe if we follow universality, antiquity, consent.” Questions of an abstract or absolute methodological sufficiency of such a statement aside (cf. qualifications on both the Orthodox and Roman Catholic side, e.g. by Fr. Florovsky, Cardinal Newman, etc.) we see especially in the early period that as opposed to the communities which were planted directly by the apostles themselves in cities with large communities from the early New Testament period, heresy was marked by isolation and fragmentation (cf. αἱρέσεις is often rendered as "factions"): isolation in time (e.g. believed later but not early), isolation in person (ideas which arose with single individuals, often designated by their being named for individuals, e.g. Sabellianism, Arianism, etc.), and isolation in geography (for comprehensive treatment of this aspect, see the EXCELLENT Thomas Robinson, The Bauer Thesis Examined: The Geography of Heresy in the Early Church
, still unsurpassed and a fabulous cure for a lot of errant nonsense that has been written more recently, e.g. by Pagels, Ehrman and others -details on my blog. Note also that additional complexities and qualifications arise in connection to later periods]. This continues to feed back to the early sense of αἵρεσις in the LXX, "found occasionally in the general sense of 'choice'"; elaborations are not in all cases complete disjunctions (I'll spare the technicalities for the present scope). Heresy is typically seen during the period as some form of idiosyncratic choice which does not reflect the phronema or mind of the Church (for the Orthodox understanding, cf. Jaroslav Pelikan, The Christian Tradition: A History of the Development of Doctrine, Vol. 2: The Spirit of Eastern Christendom (600-1700)
, chapter 1). A key issue later was what constituted this phronema, how late developing models of universal jurisdiction, papal infallibility, and so on in the medieval to modern Latin West related to it, which is beyond the brief scope of this post to consider very briefly how the basic terms were being used historiographically.
"Now I exhort you, brethren, by the name of our Lord Jesus Christ, that you all agree and that there be no divisions among you, but that you be made complete in the same mind and in the same judgment." -1 Cor 1:10
 “There was for example Hegesippus (a name which is evidently a Greek disguise for Joseph), who flourished in the middle of the second century; he was a convert from Palestinian Judaism, and one of the first Christians to conceive the idea that the true faith could be identified by ascertaining the consensus of belief in all the apostolic churches. In pursuit of this quest, he traveled from Palestine to Rome, questioning the churches which he visited on the way about the beliefs that they held, and recorded his findings in five books of Memoirs
. His conclusion was that ‘in each [Episcopal] succession and in each city the faith is just as the law and the prophets and the Lord proclaim it’ [Eusebius, Hist. Eccl
., IV, 23.2]. His Memoirs
, long since, unfortunately, lost, contained many interesting items of ecclesiastical tradition from Jerusalem and the other churches with which he became acquainted; he was, in fact, one of the first Christian writers of the post-apostolic age who tried to support his theological belief on the basis of history” (F. F. Bruce, The Spreading Flame
(Grand Rapids: Eerdmans, 1979), p. 273).