How do we know that a Halacha which is claimed to have been given to Moshe at Sinai actually was? Especially in cases where it seems to contradict the Written Torah given at Sinai?
A Halacha l’Moshe MiSinai is a law communicated by God to Moses that has no reference in the written Torah. The Rambam has a list of 31 such laws.
(Source; See here for a detailed definition, and here for an interesting discussion.)
This was basically asked to Hillel by the convert who was only willing to accept the written law. Hillel showed him, that anyone reading the Torah needs to rely on a teacher to tell them that a certain word means what it means, and so clearly there must have been a tradition of interpretation. (Shabbos 31a) That very self-same tradition, it so happens to be, not only includes translations/interpretation, but additions (halakha lemoshe misinai) as well. Once we are forced to accept one aspect of that tradition, we need to accept the rest as well.
When it comes to specific laws - it wouldn't be possible to have a written record, because these matters were prohibited to be written (Temurah 14b), and therefore we're going to have to take them on faith. There's no other way for there to be any evidence. (For example, even if you dug up tefillin from every generation since Moshe, and they were all black, I could tell you that that was merely because it was the easiest color ink to make, or traditional, but not because it was told to Moshe by God at Sinai- we have no audio recordings from that particular event).
@Shmuel, the Rambam does not say that the fact that ''an eye for an eye" means monetary compensation is a halacha L'Moshe miSinai. ''Halacha L'Moshe miSinai'' is, as he explains, a technical term for the kind of פירוש מקובל מסיני that has no Scriptural indication. The Sinaitic oral explanation that ''an eye for an eye'' means monetary compensation does have Scriptural indication.
ו אף על פי שדברים אלו נראים מעניין תורה שבכתב, כולן מפורשין הן מפי משה מהר סיניי, וכולן הלכה למעשה הן בידינו
