for the record, kematu is not 'hiding' in that cave. not only does he live there, that's his primary hang out. in fact, after the quest, he spends 6 continuous months in there. so now if the banditis showed up, it's because they're sharing kematu's cave.
Just one problem with that, bud; He still disappears eventually and the only reason they're still there is likely a bug that Bethesda overlooked. As I mentioned before, listen to what the bandits have to say when you first enter as part of the quest; neither side likes the other but, Kematu and his buddies are paying for the shelter/base of operations, but the Alik'r themselves don't terribly enjoy sharing space with bandits.
as far as who's innocent, there's no evidence one way or another.
Not necessarily.
let's assume saadia is a thalmor agent. she doesn't know who you are. she could be a double agent; this means she's actually working for the hammerfell pretending to be a spy for the thalmor. granted she's informing the thalmor - but the information she provides hammerfell is infinitely better. this would back up her swiss cheese story. since if she were both a hammerfell and thalmor spy, 1 of those truths will get her executed on the spot, gauranteed. which truth would you tell? if i were a double agent and someone in full armor and decked out weapons asks me if i'm wanted, my first reaction is to pull out a gun, shoot him, then move to another country. of course the sniffle-everyone-wants-to-kill-me-sniffle excuse coupled with puppydogeyes could equally be a viable strategy.
There is a MAJOR flaw in your thinking though; Saadia almost immediately claims that she fled Hammerfell for speaking out against the Thalmor. The Redguards of Hammerfell HATE the Thalmor and fought a long and bloody war of attrition and eventually fought the Thalmor to a standstill and forced them out of Hammerfell. There is no real reason to even consider that the nation that fought the Aldmeri Dominion and Thalmor for the longest time would persecute and chase across the continent a hosue noble for speaking out against the Thalmor.
Speaking with Kematu, he reveals that the Forebear city of Taneth would have held out if Saadia hadn't betrayed the city to the Thalmor. Furthermore, if she was truly fleeing for speaking out against the Thalmor, why would she settle in a province and city where the Thalmor essentially have free reign and mobility? There is no evidence to suggest she is a double-agent and she pulls a knife on you when you first talk to her. This is not how double-agents behave or should behave.
no evidence that kematu is or isn't an assassin.
Actually, there's plenty of evidence to suggest that he isn't an assassin.
if he wants to maintain the guise of a legitimate bounty hunter, he needs to paralyze her. for example, if he has more than 1 mark in this city, he needs to kill her on the trip home rather than near a city with witnesses; he has to maintain cover. furthermore, if he kills her in front of you, you may react badly and come after him. by paralyzing her, he has bought you as an ally and reduced suspicion of him in the entire city - optimum strategy for a real assassin. it's like a real life assassin joining the police force. when he actually kills a mark, he can use his police background to cover the evidence and use his police friends to back him up.
There are several problems with your line of thinking. Let's look at various assassins and assassin orders throughout the Elder Scrolls games. You are given a target, you generally have to be/should be discreet, and you alone do the deed. There is no need nor is there any benefit in sending a frikkin platoon of agents after a single target if the target is due for assassination; it costs more resources, is more visible, arouses suspicion, and is far more expensive and potentially unreliable.
If the Alik'r agents are assassins, they are terrible assassins. They interrogate Redguard women wherever they find them, obey the laws of the land and are more than happy to explain why instead of "none of your business". The captured Alik'r you talk to in the Dragonreach prison even talks of honour and that by being captured, he has dishonoured his comrades and will be barred from rejoining them so he will return home.
As for Kematu, the stuff you mention being "optimum strategy" is anything but, especially under the following circumstance; killing Saadia after he paralyzes her, he will say "After all that work, you killed her? You have ruined everything" There's another lore-specific reason to trust Kematu more; Redguards overwhelmingly abhor magic. Kematu uses a paralyzation spell. This has to be a rather high-priority target and the necessity to keep the target alive for a Redguard to use magic. And as I mentioned earlier, it makes no sense to send a platoon of agents who stick out like a sore thumb who openly interrogate and search for their target to be assassins.
This isn't Hollywood or TV; joining the police force to be an assassin is a TERRIBLE idea. There's so many problems with that, I don't even know where to start.
in a land of skyrim, both paths are equally irrelevant. if only 2 people in hammerfell knew of saadia's role and they were killed, she becomes effectively a fugitive. she could try selling thalmor secrets - but it may cost her her life. so now she's SOL, no practical skills to speak of to get a job, no way back into either country without being highly suspicious. 25 years ago means she may no longer have pertinent secrets and the people who knew her identity might have died naturally; this is likely the case, seasoned veterans that oversee projects are usually well aged. in a land without challenge-response key cards to verify identity, it will boil down to (s)he said.
Everything you said here could be used to argue that Saadia is in fact NOT a double-agent and effectively a Thalmor spy.
Kematu might have been chosen because of his race. in a band of assassins, he was probably trained in even hammerfell culture and speech in order to blend in. kematu's story is easily verified iff (if and only if) you can get word to and from hammerfell with an official seal. if weather or political conditions are volatile, then you, like everyone else, is playing a guessing game. assuming the hammefell government still has the personnel that remember sending kematu in the first place - if they were killed, everyone's an orphan operative.
Again, band of assassins doesn't make sense from any logicial, logistical and tactical point of view. Why train someone to be all those things when you can go to Hammerfell and get the real deal for cheaper? It also makes no sense since ALL of his agents are Redguards and ALL of them are wearing the garb of the Dunedweller Redguards, who in habit the Alik'r Desert. If you side with Kematu and help him capture Saadia, he says the following:
"Don't allow yourself to be fooled by a pretty face again, you're better than that."
and...
"The resistance against the Thalmor is alive and well in Hammerfell, friend."
And finally, the BIGGEST reason to trust Kematu is this:
Spoiler By siding with the Alik'r agents and delivering Saadia to them, Thalmor agents begin to come after you. This confirms that she is in fact a Thalmor agent and NOT innocent.