How would a Rabbinic Jew refute the Karaites claims? That they're the original Judaism? That their customs are correct and ours are wrong? Will you please provide sources too?
[I apologize that the answer came out so long. It's a complex subject in my opinion, and so a lot of ground needed to be covered].
I have been thinking about this question for several days now. I was trying to decide whether the answer should be a really easy one, for the impracticality of the halacha of early Karaites (which, for this exact reason, is not kept by modern Karaites) and for the sources later ones used to explain their history, or a difficult one, for the complexity of some of the roots of early Karaite and pre-Karaites (but still not Rabbinic) theology. Not for nothing, the Geonim and the Rishonim had a difficult time holding off Karaite influence, and again, not for nothing, at one time, the Karaites comprised some 40% of the Jewish people (!). If it was truly so simple to disprove their claim, I would think that it would have been easier to "defeat" them, so to speak (though I may be mistaken about the rationale1). On the face of things, the problem is that we're dealing here with tradition and without a time machine or nevuah, disproving tradition is difficult. However, in the Karaites case, this may not be quite so difficult. Let me explain:
The modern consensus among scholars is that the Karaites weren't started by Anan ben David (and so say the Karaites nowadays as well). Rather, Anan's group of ex-Rabbanites, the Ananites, joined up with some of the remnants of various older Jewish sects, thought nowadays to have been the spiritual descendants of, among other groups, certain Second Temple-era sects such as the Qumranites. Qumranite influence can be seen by various terms Karaite texts have that were then found, over the last 75 years, in the Dead Sea Scrolls (see for example Prof. Yoram Erder here and here) and by the testament of Yaakov Qirqisani, a 10th century Karaite, who, when speaking of the views of Binyamin Nahawandi, probably the most prominent of the second-generation Karaites, said2 that those views were similar to the views of "the Magarites" (אלמגאריה), which means "cave people" because their writings were found in caves - this is nowadays thought to be one point of evidence that earlier Jews also found some of the DSS (for a summary of other points, see here). Qirqisani also mentions some of the other early Karaites who today are thought to have been members of other sects that had joined together to form the Karaite movement.
Qumranite influence upon Karaite theology is problematic because I'm not sure we know enough about the Qumranites in order to disprove their views and traditions. This is the difficult aspect of the answer. The flip-side of the matter is that it seems that Qumranite theology mostly influenced the fringe Karaite groups, such as the one led by Yishmael the Akubarite, or even prominent ones, such as Nahawandi's, but Nahawandi's influence died out quickly, which shows that his views weren't too popular in the long run. The bottom line is that mainstream Karaism (as much as any part of Karaism may be referred to as such) may have still borrowed some terms, but that's pretty much where the similarities end. As Natan Shur put it in his book "The History of the Karaites", pg. 19 (my translation):
"Against the argument that there's a connection between the Karaites and the Dead Sea Scrolls stand a number of heavy-weight counter-arguments, and these are:
Qirqisani the Karaite does not give the discovery of the ancient manuscripts any particularly special attention, and in fact, he believes that most [of what was found] were nonsensical. Besides, the discovery of these scrolls was not mentioned in any other early Karaite source.
The faith that is presented in the scrolls, the faith in pre-determined fate, does not line up with the commonly-accepted Karaite faith - the belief in free will.
- The poor Hebraic stylization of the scrolls hints that their authors didn't study Tanach very deeply. The Karaites, on the other hand, placed the Tanach in the center of their faith. [...]
And so forth. And he concludes (pg. 20):
"...From here we see that at this stage of the research, it is difficult to conclude that the DSS had any direct influence upon early Karaism..."
As I said, mainstream Karaism almost certainly had little to do with Qumranism.
So what exactly is "mainstream Karaism"? The Ananites perhaps weren't the central Karaite group at first, but by the tenth century, they were considered the forefathers of Karaism and from this time onwards, Karaism was heavily influenced by the Ananites' teachings. This leads us to the simpler aspect of the answer: Disproving the roots of mainstream Karaism. This is divided into two points: The impracticality of early Karaite halacha and the sources later Karaites use to explain the history of the movement.
1. The impracticality of early Karaite halacha - early Karaite halacha was essentially a free-for-all, anything-goes sort of school of thought. As the Rambam put it in his commentary on Avot 1:3:
"...And they are called Karaites in these lands - I mean to say, Egypt. And their names among the sages are Sadducees and Boethusians. And they are the ones that began to question the transmission and to explain all of the verse according to what appears to them without listening to the sage at all..."
And in an anonymously-authored anti-Karaite polemical manuscript, it says:
"They [the Karaites] are loyal to a view that can be summarized per their saying: "one Torah and one law". They deny any book written per Oral Torah explanations and not per the Written Torah. They, in any case, create a variety of books, differing commentaries and explanations that dispute one another. It began with Anan, continued with Binyamin, and Malach, one after the next..." (English translation per the Hebrew translation here, pg. 96)
"Lacking any sort of binding tradition or authoritative body in charge of deciding the halacha, any Karaite author was free to interpret the text as he wished..."
This is of course a major problem for Karaite theology, for two reasons: a. It is obvious from Devarim 17:9-10 that there must be a governing body and a widely-accepted interpretation of the law. b. If it was truly the case that since the giving of the Torah in Sinai, any man was free to interpret the Torah as he saw fit, then how is it possible that generations of prophets rebuked Am Yisrael for not keeping the Torah?! After all, any man could approach the prophet and tell him: "Excuse me, who are you to say that I'm not keeping the commandments? I keep them as I see fit!"
Later Karaites apparently came to these same conclusions, for they began to institute new rules within Karaism, so that not every interpretation was truly acceptable, at least in practical terms. And they also created governing bodies - the "Chachamim" as they call them. Nonetheless, this aspect of their roots appears to have been refuted.
2. The sources later Karaites use to explain the history of the movement - strange as it may seem, Karaites from the 10th century and onwards used Geonic and Rishonic Rabbinical writings as a basis for their accounts of Karaite history. For example, many used Rihal's version in the Kuzari (see here, pg. 14, right column). This is problematic on their end, because it shows that they had no non-Rabbinical sources to tell the story of how their sect came to be. And since they contended that the Rabbanites invented things such as the Oral Torah, how could they trust their historical accounts, which are part of the Oral Torah?
Therefore, the other aspect of their roots has also been shown to not hold any water.
To summarize: There are some aspects of early Karaism that we do not have enough information about them to properly refute them. But the central tenants of early mainstream Karaism can be refuted in my opinion, and these - in particular the first point - were indeed subject to the continuous attacks of the Geonim and Rishonim.
1 Perhaps most Jews weren't drawn to them because of their logic but for other reasons, such as frustration with the contemporary model of Jewish leadership. There were also times in which some Karaite communities told European Christians that they weren't Jewish, and so received more lenient treatment from the Christians. Some contend that most cultic Jews were simple people with little theological knowledge and were simply drawn to the messianic façade displayed by the charismatic leaders of these sects.
2 As far as I know, Qirqisani's book "Kitab al-anwar wal-marakib" on the history of the Karaites has yet to have been translated into Hebrew or English, so quotes from his book come from those that studied the original Arabic.
Karaites don't believe the oral law. Many things in the Torah can't be understood without the oral tradition. For example it says to wear totafos between your eyes. What are Totafos? Without the oral law, the Torah can't be understood. It says a person who does "work" on Shabbos is put to death. What defines work.(I once asked a Karaite this question and he said he was wondering the same thing.)
Without the oral tradition you just give your own interpretation what the verses mean. That would lead to thousands of interpretations, without knowing which is right. Obviously the Oral law was given with the Torah, since if not for it, people wouldn't understand the Torah. Therefore obviously people who claim that the oral law is fake can't be the ones that received the Torah. (Or they were Jewish and started a new cult, denying the oral law...)
If you are looking for a refutation with sources see the Sefer Kuzari Sheni.
If you want a more simple one just use the following observation. Karaites barely exist. Ditto for Samaritans and Sadducees and other group that rejected Rabbinic traditions. (there have been others over the millennia) If the groups who reject rabbinic law represent the divine will why do they appear and disappear over time? Shouldn't the groups who truly who represents Gods will remain eternally?
(the main point is that the Sefer Kuzari Sheni gives the sources answer in Kariate claims. I won't debate the second proof)
הלל הזקן was as a rabbinic jew as you can find and he already basically answered this question, see shabbos 31a
ת"ר מעשה בנכרי אחד שבא לפני שמאי אמר לו כמה תורות יש לכם אמר לו שתים תורה שבכתב ותורה שבעל פה א"ל שבכתב אני מאמינך ושבעל פה איני מאמינך גיירני ע"מ שתלמדני תורה שבכתב גער בו והוציאו בנזיפה בא לפני הלל גייריה יומא קמא א"ל א"ב ג"ד למחר אפיך ליה א"ל והא אתמול לא אמרת לי הכי א"ל לאו עלי דידי קא סמכת דעל פה נמי סמוך עלי