The short answer is no, there were no criminal records or death certificates in the Middle Ages and no one really had any interest in keeping track of criminals, at least not in any of the sources I've come across.

The main reason for this is that the medieval concept of criminal justice was quite different to ours. There was no distinction between 'criminal' and 'civil', as we have today; even for a crime such as murder, you had to be brought to court by another private individual. For the vast majority of the Europe in the Middle Ages, crimes were resolved via compensation or arbitration (such as Anglo-Saxon wergild, although there are analogues across early Medieval Europe.) Once you had paid your compensation to the person you had harmed (or their family), you were free to go. There was no concept of being an 'ex-con' or anything specifically criminal about you, although you'd certainly have a reputation and people were unlikely to forget what you had done in the close-knit rural world of medieval Europe.

The closest thing we do have to criminal records are the records of court cases. Many of these are what we would nowadays call civil cases, often disputes about ownership of land and property, particularly those surviving from the earlier part of the period, since courts did not keep systematic records and so all we have are chance survivals of judgements preserved by the parties involved. By the later middle ages however (13th-15th centuries), court records start to be preserved in large numbers and we can get a much better idea of the role courts played in everyday life. 14th and 15th century England, in particular, has a huge amount of this material - hopefully someone who knows it better than I do can write in a little more detail about it.

Just a caveat about what I've written above: since it's trying to summarize a thousand years of history across a continent, there are, of course, going to be significant temporal and geographical differences, not least when it comes to the preservation of the sources. But as a general overview, I think it's sound.

In the Netherlands from as early as the 14th century there was sort off a way of keeping record of crime. Mostly thief's and repeat small offenders where branded with the seal of the city that the criminal was caught in. In this way if a criminal would go to a different town or city they would know he/she was a criminal. This was of course a crude way of keeping track but none the less practiced until the late 1700's.

It was practiced in that form until the french invaded and created the Batavian Republic circa 1795 when it changed from city seals to numbers associated with certain crimes. It was finally abolished around 1854.

Sources: http://gevangenpoort.nl/strafwerktuigen Site in dutch belonging to a museum about crime and imprisonment in the city of Den Hague

Apologies for grammar.