Always? No. Dumbledore was fooled all of 4th year when Barty Crouch Jr impersonated Mad Eye Moody. He simply is always unbiased and uses logic. In the other answer, this is shown in all cases:
“He did not wish to tell me,” said Dumbledore. “But I am a sufficiently accomplished Legilimens myself to know when I am being lied to and I — persuaded him — to tell me the full story
He probably knew right away that Kreacher would never tell him what he wanted to know. He probably asked nicely, then used Legilimency to get the knowledge that he wanted.
“I must ask you, Harry, whether there is anything you’d like to tell me,” he said gently. “Anything at all.”
He also knows here that Harry won't tell him anything. He's simply testing whether or not he's trusted by Harry. And he isn't.
And all the cases in your question:
He believes that Harry isn't opening the Chamber of Secrets, without asking a single question.
Ah yes, a 12 yo that has next to no knowledge of parseltongue is 1) The heir to Salazar Slytherin and 2) Is opening the chamber regularly and killing people. Makes perfect sense. He of course surmised that this had to do with Voldemort and when Harry brought the diary, he put the pieces together
He believes the trio in Prisoner of Azkaban, when they claim that Ron's rat Scabbers was actually Peter Pettigrew, and that Sirius Black is innocent. He asks no questions and jumps straight to the fact that nobody else would believe them.
Harry's been getting told this entire time that Black is out to get him and that Black killed his parents. So him, along with Hermione (the actual smart one that goes by the book) and Ron (the loyal friend) all saying that Black is innocent? Yes, that's not too hard to believe. Problem is proof is required and they have none.
He believes Harry when he returns from the graveyard in Goblet of Fire, having no doubt that Voldemort had returned.
Not 100% at the time though. He would need confirmation of some sort. He gets it when he interrogates BCJ and he says something along the lines of "You know what this means don't you? The Dark Lord has returned!" So Harry saying he's back, a loyal Death Eater that's saying he's back, and the Dark Mark is clear as day? Not hard at that point to realize Voldemort's back.
In Half-Blood Prince, he's aware that the memory he got from Professor Slughorn is a lie. Even though Slughorn (a pretty powerful wizard) thought he could deceive Dumbledore - otherwise, why give the memory at all?
He had been working on Voldemort for a while. Chances are he didn't initially think it was a lie but after discovering what Voldemort had done and how he'd done it, he probably realized that there's a missing link-and the memory was it.
I forgot that in the book, both Harry and DD recognize that the memory is a fake due to it having different qualities than other memories. Perhaps Slughorn was hoping to fool DD despite the bad memory. He also knew that DD would be coming back for the memory evidenced when Slughorn gets super defensive when asked about it by Harry.
There may actually be more cases than this but being unbiased and using logic were actually quite powerful for him. With one half of the population being out of the loop and the other half scared to death of something whether it be a basilisk or a serial killer or Voldemort, it's easy to see how DD was able to 'see through' everyone.