Such agency will have hard time building trust (especially given it's a government agency - modern governments aren't particularly good at building trust), and it could lose it all over a single honest mistake, or (as we're talking about conspiracies here) some sort of a poison pill dataset.

Neither does censorship, of course - if anything, it fuels the conspiracy.

What works is education, in general. The better the quality and versatility of education, the higher are the chances an alarm would ring in person's head when he reads some controversial statement. But quality education is an extremely hard and costly problem.