Another way, which I used in a game some years ago, depended on the fact that you actually have to ask the suspect a question before you can determine whether or not his answer is or is not actually true. You lose the problem of information you receive possibly not being accurate, but that doesn't obviate the problem of needing to receive information in the first place, or needing to receive the right information, or needing to put said information together. You've still got to work out what questions to ask, in other words.
In fact, the detective character in that same game could also pull information directly from someone's head via magic, eliminating the problem of asking the right questions- but even then there's still a lack of information. Each witness only saw a bit of the actual circumstances surrounding the crime, and none of them had actually seen the murderer.
Of course, once they found a suspect (by noticing that the victim owed a certain gentleman rather a lot of money before he died), confirming that he did the deed was simple- or rather, would have been simple, had the murderer not had a few tricks up his own sleeve, such as invisibility. Can't ask him if he did it if ya can't actually find him.
In short, a story that works in one world with certain rules may not work in another world with different rules, at least not with some modification. The plot to Magnum PI wouldn't work in a setting that has cell phones because it was designed for a setting that did not. So ignore the problems that are solved by the presence of easy communication and add some new ones- perhaps even some that are caused by that same convenience.
Remember that solutions to a problem can often cause problems of their own: magic solves the problem of verifying information, but it also introduces the problem of your murderer being able to strangle his victim without actually being in the same room.