So, I absolutely think that we should go with the "convince me" plan first. After that, though...
"Very well, Hideki-san. I have arguments to make. Will you allow me the time to make them?"
I started writing this out, but it started getting Looooong (as my stuff is wont to do) so I'll break it down into logical arguments instead, and perhaps we can boil it down later.
Basically, there are three basic possibilities from his perspective. One is that we're loyal, and he should probably let us live. One is that Soshi Naoto was loyal, and we're the bastard who killed him and took his place. One is that Soshi Naoto is disloyal, and needs to die for killing his lord.
Our answer to "killed him and took his place" is the relatively straightforward shared knowledge thing. By now we have a fair amount of shared history with Pale Oak that neither of us has shared with anyone else. As long as we can be sure he is who he says he is, we can just answer questions about that shared history until he's satisfied.
Our answer to the other is that this attack on the embassy... well, it took a lot of doing. It took out Bayushi Kimoko and Yogo Hanzo, while this guy was fighting next to them. We don't know how many were involved, but there had to be a decent number of them, and reasonably effective combatants. Soshi Naoto - Scorpion Bushi fresh out of his gempukku - doesn't have anythign like the assets needed to make that happen. If it was some shadowy, non-Scorpion overlord, then the position I've gained isn't anything like worth the cost in manpower and secrecy (for whoever it was) that they paid to make it happen. The *only* way that the attack makes sense is that somehow it was being done to try to shut down the Scorpion embassy because we were being too successful at somethign or otherwise thwarting plans, and from that perspective, the stuff most likely to have been thwarting their plans was the stuff that Soshi Naoto himself was pulling off. Yogo Hanzo was certainly useful, and a meaningful contributor to the team, but he wasn't doing anything particularly earth-shaking. Bayushi-sama's blood-soaked romance with Matsu Ketsui was adorable and impressive in its own right, but it wasn't exactly disrupting any carefully laid plans. "Pale Oak"... well, we don't actually know all of what he was doing, but if they'd just wanted to shut *him* down, surely there were easier ways than trying to go through Bayushi Kimoko to get to him.
Us presenting this in our overly-rational, overly-analytical way would probably *also* help convince him that we are who we say we are... and the way that we were pretty clearly being Honorable Scorpion before all this happened should make "and now we betray our Lord" seem *unlikely*.
Could probably shorten it up at least a bit with some sort of "which would you like me to address first?"