Sense Motive isn't magic. Even if totally reliable, it can only detect deliberate and knowing attempts at deception. A character who lies but believes he is telling the truth and characters who are pathological liars should both register as 'truthful'.
A character who has built such a character has earned the right to be able to use his ability to "read" people so well as one of the 'tools' in his adventuring kit. One should no more think of it as "unfair" for a character to have such a good skill bonus than to think it "unfair" for a character to cast such good spells to blow away hordes of critters or to be able to knock down the best kitted-out NPC with his wedge of steel.
I agree with all of this. And the rest of the post, too

, but especially this bit.
Problem arises when the player says : "Are you the one who killed the king ?" ["I use sense motive with my +10 oversight bonus"]
I can't really answer that with something else than yes or no:
"I did not kill the king and I ate chicken today." [You sense only half is true] xD
But then the pc can do that with every major NPCs and the plot twists possibilities are reduced..
There are lots of ways to deal with this.
The first and most obvious is simply to have the NPC not answer - "how dare you ask me that?"
Alternately, have the NPC simply change the subject.
Or, have the NPC admit it... and then call his guards to have the PCs killed. Or, indeed, just point out that they need to be able to prove it, and they can't.
But there's another important key to the "murder mystery" scenario that gets missed far too often in discussions in the D&D context (both in relation to Sense Motive, and indeed to alignment as a whole):
everyone has secrets.
If you run a mystery in which there are a bunch of entirely innocent NPCs and one BBEG, you're going to have a pretty damn short and unsatisfying adventure. The paladin uses
detect evil, the walking lie detector uses Sense Motive, or whatever, and pretty quickly the truth comes out. Done.
A better approach is this: everyone has secrets. Everyone tells lies. And there need to be villains around who are nothing at all to do with the matter at hand.
So when the PCs start asking about what the seneschal was doing on the night of the murder, he proceeds to get oddly evasive. But not because he's the killer - he doesn't want his affair with the cook's wife to become public knowledge.
When the PCs ask the captain of the guard, he tearfully admits to being responsible. But that's actually not true - he's just overwhelmed by his guilt.
"Everyone lies. The innocent lie because they don't want to be blamed for something they didn't do, and the guilty lie because they don't have any other choice."