What non-Catholic Christian groups existed in Western Europe during the Middle Ages? Between the fall of the Western Roman Empire and the Reformation, were there any Christian groups outside the Roman Catholic Church? Who were they?
Taking your defined period for the Middle Ages—starting at the fall of the Western Roman Empire in 476 CE and ending with the 95 Theses in 1517 (which began the Protestant Reformation)—a number of minor Christian groups that were considered heretical, and thus outside the communion of the Catholic Church, popped up. 

Given the definition of Catholicism, anyone who does not accept the entire Dogmata of the Church would not be in communion with it. It would therefore be impossible to enumerate every single person or minor group in a 1,000 year time span who may or may not have been in communion with the Church during that time period. However, it should be noted that the Church, from time to time, did address these heresies in the form of Synods, Ecumenical Councils, Papal Bulls, Encyclicals, and so forth.

Among the points of contention in the Middle Ages were the following:


The Investiture Controversy, where Kings and Queens were creating their own bishops and priests (a power reserved only to the Pope), addressed in the First Council of Lateran
The Antipope Anceletus II, pretender to the Papacy; addressed in the Second Council of Lateran
Catharism (also known as the Albigensian Heresy), a gnostic sect in France, addressed in the Third Council of Lateran
Waldensianism, which practiced something similar to sola scriptura prior to the Reformation, also addressed in the Third Council of Lateran
The Knights Templar, which were found to be a heretical order after the Crusades, and disbanded by the Council of Vienne


Those aside, there were two major events, or schisms:


The Great Schism of 1054: Brought on by a number of issues, the Eastern Eurpean Churches, centered around Constantinople (now the Orthodox Church, or the Eastern Orthodox Church), fell out of communion with the Western European Churches (now called the Roman Catholic Church).
The Western Schism (1378–1417): Due to a political issue with most of the major powers in Western Europe, three Papacies, all laying claim to the Church, arose: one out of Rome (backed by the Holy Roman Empire), another out of Avignon (backed by France), and a for a short third out of Pisa (backed by a small number of cardinals and bishops).


It's important to note that, like the Protestant Reformation that would come a few hundred years later, in both cases, all sides laid claim to Catholicity and considered themselves Catholic due to the First Council of Constantinople, which established there is only one Holy, Catholic, and Apostolic Church.