It can come as quite a revelation to some that our brains just aren't very good at self-monitoring for accuracy purposes! The very premise of evolution is that, if something works, we'll keep it thanks, and if it doesn't, we'll get rid of it. And the fact that our brains have evolved, means we're stuck with that ad hoc pragmatism in the makeup of our very selves.
There's sometimes a danger in evolutionary psychology, though, to make 'just-so stories' out of these themes - to cobble together a plausible story as to why we seem to have a certain cognitive mechanism, or why we act in certain ways and call it science. It has to be accompanied by proper empirical evidence based in existing theory to actually mean anything, and some are a bit guilty I think of assuming plausibility is a substitute for evidence. There's no excuse for it now, I don't think: evolutionary psychology is coming of age, and there are now lots of researchers concentrating on producing falsifiable hypotheses, rather than evolution-flavoured fairytales. John Archer is just such a chap, having written extensively on this stuff.
But absolutely, in terms of 'changing hearts and minds', this stuff needs to be borne in mind. There's a temptation, certainly something I'm guilty of, to assume that, if you rationally point out the flaws in someone's arguments, or the problems with their conclusions, you're justified in your surprise that the reaction is "well I believe it anyway" (or more commonly, "well, shut up.").
Cognitive dissonance is a particularly annoying phenomenon: the way one's mind copes with an 'invading' thought, which challenges the ones you've invested in already. It's like the memetics idea (see e.g. Susan Blackmore's extensive writing on this) - if someone's mind is in the grip of a 'viral' idea, and you introduce a new one, there'll be a scrap to see which is stronger. And the sad fact is, that accuracy≠strength - the catchiness of the existing belief, its pithiness, congruity with existing world view, the previous investment one has made in that belief already, are all things which will beat off a new thought. Not to mention more general beliefs about what it means to change one's mind, what it means to lose an argument, etc.
An effect I've observed quite a lot of times now, though, is that critical thinking can be a sort of dormant virus. It doesn't replace the thought you were challenging in someone with no history of ever thinking critically in their lives, but suddenly, surprisingly to all concerned, kicks in when a new weird belief comes along.
Several people I've spoken to (and like you, John, I prefer a reasoned, rather than an antagonistic approach usually) have said "well look, I don't care that there's no evidence for leprechauns, I have one in my garden and that's that", and yet the next time a new belief comes along, which they haven't invested in, or built a little house for, they can boot it out straight away as daft.
Mysterious creatures, we.