I think the whole point is not that valgrind is lying, but that people do not do complete white box testing. If there's a bug in some place the program doesn't go very often and no tool looks at that, everything is going to look fine. When a tree falls in the forest and no one is around to hear it...