Of course we as players know how a Focus works - but the characters don't know about xp and Virtues. All they know is that the Tremere come out of their apprenticeship well prepared for certamen, because it's something they care about, while others care about Magic Theory or Ignem.
Of course they are good at certamen, it's their House virtue. The same way that a Bonisagus is good at Magic Theory. Everyone knows they have an edge at certamen. But they are not unbeatable. Everything you said also goes the other way around. Other Houses have certamen specialists as well, they can put in the work to find their opponents weaknesses etc. Most Tremere don't look like the one you sketched. People do win against the Tremere.
So they are better than most, because it's something they care to be good at. They are not invincible. So "I don't want to fight the Tremere, he's too strong for me" doesn't sound like something many mages would say (maybe they would think it, but that doesn't change the role of certamen in Hermetic society).
The comparison with Bonisagus is probably why Bonisagus as a house is not a problem : anyone can take puissant MT (or puissant intrigue). For them it's free.
But nobody else than a Tremere can take the minor focus certamen because it's for Tremere only. So you cannot pay for it in another house. And if I personaly find easy for magi to leave some houses for others, we all know that Tremere is not a house you leave intact and no traitor would probably survive long enough to pass the secret of the focus outside.
Again, it's beside the point. It's not that Tremere are somehow "cheating" at Certamen. Heck, we know from the rules in Apprentices for learning House Virtues that the focus is the result of training from their parens in some sense. Even if you let other magi take the same focus (Merinita from the line of Muj for example) the problem is that the ability to be much better at Certamen than you are with your Arts generally, undermines Certamen as a proxy for magical conflict. A Certamen Ability or whatnot would create the exact same problem, it's just highlighted because the effect of a magical Focus is so large.
Certamen is not a proxy for magical conflict. If a Merinita beats a Flambeau in certamen using Intellego Herbam, does that mean he would win a Wizard War? No, the outcome is completely uncertain because it depends on so many other factors.
Certamen is a comparison of magical power. You basically choose two Arts and compare how good you are at them.
It doesn't need to be a proxy for a Wizard's War, because you wouldn't go to war over most issues resolved by certamen. It fulfills a role that cannot be filled in another way.
Whatever role you think Certamen ought to have, doesn't this rather strengthen my point that once you introduce a Focus in Certamen, it's not a sound comparison of magical power anymore?
Which is only relevant if you believe certamen should be a valid comparison of magical power.
On the other hand, belief that something measures something else does not mean it has to actually do so. People have long mistaken an ability with chess for a general quality of intelligence. Similarly some groups believe that shooting at unmoving targets while dressed in camouflage is a measure of actual military capability. Certamen settles disputes, and serves the role of "dueling" in a non-lethal capacity within the order. Some within the order may believe it means more than that, for others it may have no more significance than getting high score in pac man or pinpball.
Per HMRE (p116-117) the Tremere aptitude for certamen isn't from studying or practicing certamen; it's a "partial integration in progress" of the Nightwalker virtue.* The implication being that Tremere was himself a Nightwalker since he helped Bonisagus develop certamen. For all we know Tremere apprentices may be proto-Nightwalkers, or the House has a mystery initiation for it or something.
* Whatever that means; "partial integration in progress" isn't something that the Integration rules have as a possibility.
Puissant MT is a +2, Puissant (Art) is a +3.
That looks a lot like Potent Magic (certamen) and its +3.
Tremere House Virtue is strong in an excessively narrow field. This implies a strong limit on certamen bullying. If it happens too often, it becomes too strong to be minor.
So the question becomes: why isn't certamen not a big issue?
If you believe there are cultural limitations to certamen, mMF is fine.
If you believe certamen is prevalent, change it to Potent Magic.
At a fundamental level Certamen can only be used to bully other magi of the order. The dragon or the Augustinian brotherhood will tell you where to stick your certamen specialization...
Apprentices says on p. 42 that for House Tremere, the House Virtue is "learned over time", and "it takes 10 seasons of one-on-one interactions with a parens for an apprentice to gain the Virtue". Only the Mystery Cults and some Ex Misc undergo an initiation.
The way I get my head around it, is that it does sort of act as a proxy for magical power: The power you get from a unified house, so if someone goes against a Tremere in a wizard's war, then they have to be prepared to be served with more wizard's war declarations from other Magi who they don;t even know, and can't prepare against.
Two things occur to me, looking at this without any desire to maintain or justify the current reality in Mythic Europe.
A certamen duel can be forced on you and you either concede the thing the disagreement is about (which may be a political vote or other thing of some importance) or risk loosing it anyway and perhaps more if the victor gets creative with their right to cast a spell on you.
And secondly the Order is supposed to be one household, one nation, a place where you do not step out of the bounds of civility and politeness. No Hermetic Magus should regard another as a target to be bullied into compliance. (Yes, there is Wizard War but I would argue that it is even more bound about with law and custom than certamen.)
I wonder what would happen if a popular or politically powerful magus were to say: "I didn't hear that challenge. I do not admit it ever happened. I will not give you your 'prize' and if you dispute what I say you can bring a case against me at the next Tribunal. In about six years and two months. Good day!"
There are constraints on using certamen on votes, and you cannot be forced to surrender a right. Certamen is for disputes of honor and to settle matters too trivial to trouble a quaesitor or tribunal.
Certamen use seems to vary a lot; I can't think the last time we had one, or considered it, or even talked about it. We've had a Wizard's War and murders, between NPCs, but no certamen.
I think this quintessentially nails down why the Tremere Certamen focus is not "unfair": Tremere are stronger in Certamen than their raw Art scores would suggest (thanks to their Focus) just as they are stronger in Wizard's War than their raw Art scores would suggest (thanks to their militaristic House standing unified behind them).
My read on "Partial integration" is that (and it's a little fuzzy I admit) is that during integration you can create discrete effects as part of the breakthrough. So, Tremere/Bonisagus may have invented ~15-20 breakthrough points worth of effects, but not enough to fully integrate Nightwalking. Eg, a lot of the things Nightwalkers get up to fall under In/PeMe and In/PeVi, and creating the Phantasticum is definitely Muto or Creo-something, although what on earth the Phantasticum is made of is I couldn't tell you. Mentem? Vim? Aether? I guess we'll never know, since they never integrated it fully.
But maybe those notes could be found somewhere, and then we're only another 25 Breakthrough Points away...
The bit I look forward to is integrating the 'Spirit Battle' aspect, to allow one-vs-many and many-vs-many Certamen. The 'Spirit Travel' and 'Influence Dreams' abilities both have some allure as well.
What do Fertility Battles look like when it's not good v evil, but two sides of some academic point? The winning side produces extra Vis that year, or gets to roll twice on Experimentation and take the result they like more?
A bigger breakthrough could lead to the winning side getting a benefit. Maybe some of the Learned Magician Fortunam effects? Excitingly non-Hermetic stuff, I would think.
I made Certamen work at least a bit better in my game by moving it all to Characteristic+Ability for each trait rather than Technique+Form. This reduces the range of difference from a senior magus vs junior magus (theoretically), and with a d10 stress die, even a well built Tremere can lose to a lucky young magus. Tremere get a flat +2 to each Certamen trait, and I large resolve it like combat. This also means has Tremere favors learning Hermetic Abilities, at least to a more competant than average baseline.
This likely isn't a fit for everyone, but it works for me. What doesn't seem to work is the strong abusing the weak, which, in the ORder of Hermes lore, does seem to a problem of Certamen in the Order's history over time. And likely, is made this way on purpose. The problem is, for New PCs favored to lose, theoretically, on average, to more senior magi, it does not make it a fun proposition from a play point of view.