Finding the contradictions and then showing the lies are the two areas I'm having the most trouble with. I originally thought I'd have a clue combiner where you take two clues and find a discrepancy between them, but you could just brute force that like inventory puzzles in Monkey Island. And while I actually enjoyed doing it in Monkey Island I don't think it'd work here.
Papers, Please got around the brute forcing by having a timer so you couldn't go through every last thing every time or else you'd never get through enough people to have money.
So the main thing I'm considering is just copying the L.A. NOIRE system where, you win a case by using clues in dialogue bosses. In L.A. NOIRE every conversation/interrogation had stages where you could win or lose by choosing one of three options: Truth, Doubt, Lie. And with Lie you'd use a clue against their story. I think I'd make it a little less gamey by giving hte player a number of responses to choose from, or use an item from your logbook of clues. Kind of like
Grim Express, but Grim Express still had the problem of brute forcing since you could ask anyone anything about your clue book at any time in any order.
I mean really though, it mostly comes down to the writing and staging of each case to begin with. It could get really complex or keep it fairly simple about how you reach a conclusion. If the writing/logic behind it is bad the game mechanics won't help.